A225926 Least 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

Offset

1,2

Comments

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

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

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

Links

Table of n, a(n) for n=1..90.

Example

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

Prog

(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;
}

Crossrefs

Cf. A025475, A225927.

Sequence in context: A282905 A063274 A274459 * A354761 A351064 A339822

Adjacent sequences: A225923 A225924 A225925 * A225927 A225928 A225929

Keyword

nonn

Author

Alex Ratushnyak, May 21 2013

Status

approved