%I #7 May 23 2013 13:28:40

%S 0,0,0,1,0,0,0,1,1,0,0,2,2,0,0,1,2,2,0,2,3,3,0,2,1,3,1,3,2,4,2,1,2,2,

%T 2,2,3,3,3,2,2,3,2,3,3,4,3,2,1,2,3,2,2,2,4,3,2,2,2,3,3,3,3,1,2,3,3,2,

%U 3,3,4,2,2,2,3,2,3,3,3,2,1,3,3,3,2,3,4,3,2,2

%N Least number of prime powers greater than 1 needed to sum up to n, or 0 if n cannot be represented as a sum of prime powers.

%C Nontrivial prime powers: A025475 except 1.

%e 26 = 9 + 9 + 8, three summands, so a(26) = 3.

%o (C)

%o #include <stdio.h> // GCC -O3

%o #define TOP (1ULL<<15) // ~140 seconds // (1ULL<<17) is ok

%o #define TOP2 (TOP*TOP)

%o typedef unsigned long long U64;

%o int compare64(const void *p1, const void *p2) {

%o if (*(U64*)p1 < *(U64*)p2) return -1;

%o return (*(U64*)p1 == *(U64*)p2) ? 0 : 1;

%o }

%o int main() {

%o U64 i, j, k, p, pp=1, pfp=0, *primes, *pwFlat = (U64*)malloc(TOP*2);

%o primes = (U64*)malloc(TOP2);

%o char *c = (char*)pwFlat, *f = (char*)primes, *ff;

%o memset(c, 0, TOP);

%o for (primes[0]=2, i=3; i<TOP; i+=2) if (c[i>>1]==0)

%o for (primes[pp++]=i, j=i*i>>1; j<TOP/2; j+=i) c[j]=1;

%o for (i = 0; i < pp; ++i)

%o for (j=primes[i]*primes[i]; j<TOP2; j*=primes[i]) pwFlat[pfp++]=j;

%o qsort(pwFlat, pfp, 8, compare64);

%o memset(f, 100, TOP2);

%o for (pwFlat[pfp]=TOP2, i=0; (p=pwFlat[i])<TOP2; printf("."), ++i)

%o for(f[p]=1, j=0; j<=i && (pp=p+pwFlat[j])<TOP2; ++j)

%o for(f[pp]=2,k=0; k<=j && (pfp=pp+pwFlat[k])<TOP2; ++k) f[pfp]=3;

%o for (k=1; k < TOP2; k++) {

%o if (f[k]==100) {

%o for (j=0, ff=&f[k], pp=99; (p=pwFlat[j]) < k; j++)

%o if (ff[-p] < pp) { pp = ff[-p]; if (pp<=3) break; }

%o f[k] = pp+1;

%o }

%o if (k<200) printf("%llu, ", f[k] > 99 ? 0 : f[k]);

%o else if (f[k]>4) printf("\n%llu at %llu ", f[k], k);

%o }

%o return 0;

%o }

%Y Cf. A025475, A225926.

%K nonn

%O 1,12

%A _Alex Ratushnyak_, May 21 2013