A225927 - OEIS

%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