proposed

approved

editing

proposed

Not necessarily distinct prime powers, see example for a(2).

2 = 1 + 1, two summands, so a(2) = 2.

(C)

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

#define TOP (1ULL<<15) // ~130 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 (pwFlat[pfp++]=1, 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, 0, 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]==0) {

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]);

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

}

return 0;

}

proposed

editing

editing

proposed

Prime powers: A025475, which includes 1 because it includes the power 0, but excludes power 1.

proposed

editing

editing

proposed

Indices of terms Terms bigger than 4: a(340473) = a(3881313) = 5, and the next index, term, if it exists, is has index bigger than 2^34.

Indices of terms bigger than 4: a(340473) = a(3881313) = 5, and the next index, if it exists, is bigger than 2^34.

Cf. A025475, A225927.

allocated for Alex RatushnyakLeast number of prime powers needed to sum up to n.

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

1,2

Prime powers: A025475.

Indices of terms bigger than 4: a(340473)=a(3881313)=5, and the next index, if it exists, is bigger than 2^34.

26 = 25 + 1, two summands, so a(26) = 2.

Cf. A025475.

allocated

nonn

Alex Ratushnyak, May 21 2013

approved

editing