|
|
A077982
|
|
Min(P in Partitions(n), Sum(k in P, d(k))) where d(k) = number of divisors of k (A000005).
|
|
3
|
|
|
0, 1, 2, 2, 3, 2, 3, 2, 3, 3, 4, 2, 3, 2, 3, 4, 4, 2, 3, 2, 3, 4, 4, 2, 3, 3, 4, 4, 4, 2, 3, 2, 3, 4, 4, 4, 4, 2, 3, 4, 4, 2, 3, 2, 3, 4, 4, 2, 3, 3, 4, 4, 4, 2, 3, 4, 4, 4, 4, 2, 3, 2, 3, 4, 4, 4, 4, 2, 3, 4, 4, 2, 3, 2, 3, 4, 4, 4, 4, 2, 3, 4, 4, 2, 3, 4, 4, 4, 4, 2, 3, 4, 4, 4, 4, 4, 4, 2, 3, 4, 4, 2, 3, 2, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|