A347105 - OEIS

A347105

a(n) is the greatest sum of the digital roots of the individual factorizations of n.

1, 2, 3, 4, 5, 6, 7, 8, 9, 7, 2, 8, 4, 9, 8, 10, 8, 11, 1, 9, 10, 4, 5, 11, 10, 8, 12, 11, 2, 11, 4, 12, 6, 10, 12, 13, 1, 3, 7, 13, 5, 13, 7, 8, 14, 7, 2, 14, 14, 12, 11, 10, 8, 15, 7, 15, 4, 4, 5, 13, 7, 8, 16, 16, 9, 8, 4, 12, 8, 14, 8, 17, 1, 3, 13, 5, 9, 11, 7, 15, 18, 7, 2, 15, 13, 9, 6, 10, 8, 16, 11, 9

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..92.

Project Euler, Digital root sums of factorisations, Problem 159.

FORMULA

a(n) = max(DR(n), max(a(b) + a(c) for all b, c such that b * c = n and 2 <= b <= floor(sqrt(n)) <= c <= floor(n/b))) where DR(x) = 1 + ((x - 1) mod 9). - Darío Clavijo, Mar 11 2025

a(A000040(n)) = n mod 9. - Darío Clavijo, Mar 11 2025

EXAMPLE

a(24) = 11:

Factorization Sum of Digital Roots

2 * 2 * 2 * 3 2 + 2 + 2 + 3 = 9

2 * 3 * 4 2 + 3 + 4 = 9

2 * 2 * 6 2 + 2 + 6 = 10

4 * 6 4 + 6 = 10

3 * 8 3 + 8 = 11

2 * 12 2 + 1 + 2 = 5

24 2 + 4 = 6

Result is 11.

PROG

(PARI) fcnt(n, m) = {my(d = divisors(n), v = List(select(x->((x>1) && (x<=m)), d)), list = List()); for (k=1, #v, my(x = fcnt(n/v[k], v[k])); if (#x==0, listput(list, [v[k]]), for (j=1, #x, listput(list, concat(v[k], x[j])))); ); list; }

factoriz(n) = {if (n==1, return ([[1]])); my(list = fcnt(n, n), res = List()); for (i=1, #list, my(vi=list[i]); if (vecprod(vi) == n, listput(res, vi)); ); Vec(res); } \\ A162247

a(n) = {my(v = factoriz(n)); vecmax(vector(#v, k, vecsum(apply(x->(x-1)%9+1, v[k])))); } \\ Michel Marcus, Jun 06 2022

(Python)

from math import isqrt

from sympy import isprime

def a(n):

if n < 9 or isprime(n): return n % 9

DRS = [((x - 1) % 9) + 1 for x in range(0, n+1)]

for b in range(2, isqrt(n)+1):

db = DRS[b]

for c in range(b, (n // b) + 1):

bc, d = b * c, db + DRS[c]

if d > DRS[bc]: DRS[bc] = d