|
%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
|
