OFFSET
0,3
COMMENTS
For sufficiently large n, it is known that n is the sum of three primes, implying a(n) <= 6.
Goldbach's conjecture implies a(n) <= 4 for n even and a(n) <= 5 for n odd.
REFERENCES
Suggested by Amarnath Murthy.
LINKS
FORMULA
If n is prime then a(n) = 2 else if n + 1 is prime or n = p^2 for p prime then a(n) = 3. - David A. Corneth, Dec 27 2017
EXAMPLE
As 4 = 1 + 3 and d(4) = d(1) + d(3) = 3 and there is no partition giving a lesser sum, a(4) = 3. - David A. Corneth, Dec 27 2017
PROG
(PARI) A077982(n) = { my(ps = partitions(n), m=0, p, s); for(i=1, #ps, p = ps[i]; s = sum(j=1, #p, numdiv(p[j])); if(!m || (s < m), m = s)); (m); }; \\ Antti Karttunen, Dec 27 2017
(PARI)
\\ This version requires less memory:
mymin(m, s) = if((!m || (s<m)), s, m);
A077982(n) = { my(m=0); forpart(p = n, m = mymin(m, sum(j=1, #p, numdiv(p[j])))); (m); }; \\ Antti Karttunen, Dec 27 2017
(PARI) a(n) = {if(n <= 1, return(n)); if(isprime(n), return(2), if(isprime(n - 1) || (issquare(n, &p) && isprime(p)), return(3))); if(isprime(n - 2) || (ispower(n, 3, &p) && isprime(p) || bigomega(n) == 2), return(4)); c = n%2; n -= c; forprime(p = 3, n, if(isprime(n - p), return(4 + c))); return(A077982(n))} \\ Code refers to Antti Karttunen's version of A077982 above. David A. Corneth, Dec 27 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
David W. Wilson, Jun 21 2003
STATUS
approved