proposed

approved

editing

proposed

(C)

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

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

#define TOP2 (TOP*TOP)

typedef unsigned long long U64;

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

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

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

}

int main() {

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

primes = (U64*)malloc(TOP2);

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

memset(c, 0, TOP);

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

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

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

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

qsort(pwFlat, pfp, 8, compare64);

memset(f, 100, TOP2);

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

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

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

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

if (f[k]==100) {

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

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

f[k] = pp+1;

}

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

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

}

return 0;

}

Least number of nontrivial prime powers greater than 1 needed to sum up to n, or 0 if n can't cannot be represented as a sum of prime powers.

proposed

editing

editing

proposed

allocated for Alex RatushnyakLeast number of nontrivial prime powers needed to sum up to n, or 0 if n can't be represented as a sum of prime powers.

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, 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, 3, 3, 4, 2, 2, 2, 3, 2, 3, 3, 3, 2, 1, 3, 3, 3, 2, 3, 4, 3, 2, 2

1,12

Nontrivial prime powers: A025475 except 1.

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

Cf. A025475, A225926.

allocated

nonn

Alex Ratushnyak, May 21 2013

approved

editing

allocated for Alex Ratushnyak

allocated

approved