A225926 -id:A225926 - cp's OEIS frontend

A274459 Least number of perfect powers that add 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, 1, 2, 3, 3, 2, 2, 3, 2, 2, 2, 3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 3, 2, 1, 2, 3, 3, 2, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 1, 2, 3, 3, 2

Offset: 1

Sergio Pimentel, Jun 23 2016

nonn

Least number of perfect powers (A001597) needed to add up to n.
This sequence is close to but not exactly equal to A063274.
a(n) is at most 4 since any number can be written as a sum of 4 squares (Lagrange's theorem), but it is possible that for a sufficiently large n, a(n) < 4.
a(n) <= a(i) + a(n-i) for 1 <= i <= n-1. (for computational ease, the maximum value for i can be chosen as floor(n/2)). a(1991) = 4. for 1992 <= k <= 20000, there is no k such that a(k) = 4. - David A. Corneth, Jun 24 2016 [Next such k is 25887, see A113505. - Vaclav Kotesovec, Jun 25 2016]

			a(31) = 2 since 31 can be written as the sum of two (31 = 3^3 + 2^2 = 27 + 4) but no fewer than two perfect powers.

David A. Corneth, Table of n, a(n) for n = 1..10000

Cf. A001597, A002376, A002377, A002828, A002804, A079611, A063274, A188462, A225926.

Cf. A063275 (indices for which a(n)=3), A113505 (indices for which a(n)=4).

nn = 72; t = Select[Range@ nn, # == 1 || GCD @@ FactorInteger[#][[All, 2]] > 1 &]; Table[Min@ Map[Length, Select[IntegerPartitions@ n, AllTrue[#, MemberQ[t, #] &] &]], {n, nn}] (* Michael De Vlieger, Jun 23 2016, after Ant King at A001597 *)

lista(n) = {my(v = vector(n)); for(i = 2,sqrtint(n), for(j = 2, logint(n, i), v[i^j] = 1)); v[1]=1; v[2]=2; for(i=3, #v, if(v[i]==0, v[i] = vecmin(vector( i\2, k,v[k] + v[i-k]))));v} \\ David A. Corneth, Jun 24 2016; corrected by Peter Schorn, Jun 09 2022

More terms from Michael De Vlieger, Jun 23 2016

Terms from a(74) from David A. Corneth, Jun 24 2016

A225927 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.

Original entry on oeis.org

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

Offset: 1

Alex Ratushnyak, May 21 2013

nonn

Nontrivial prime powers: A025475 except 1.

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

Cf. A025475, A225926.

#include       // 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>1]==0)
    for (primes[pp++]=i, j=i*i>>1; j 99 ? 0 : f[k]);
      else if (f[k]>4)  printf("\n%llu at %llu   ", f[k], k);
  }
  return 0;
}

A290397 Least number of nonprime squarefree numbers (A000469) that add up to n.

Original entry on oeis.org

1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 2, 3, 1, 1, 2, 3, 3, 4, 2, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2

Offset: 1

Ilya Gutkovskiy, Jul 29 2017

nonn

It is conjectured that a(n) <= 5.

			a(6) = 1 because 6 is already nonprime squarefree number.
a(7) = 2 because 7 = 6 + 1 is a partition of 7 into 2 nonprime squarefree parts and there is no such partition with fewer terms.

Cf. A000469, A051034, A225926, A239508, A290136.

A354761 Least number of squares and cubes that add up to n.

Original entry on oeis.org

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

Offset: 1

Peter Schorn, Jun 06 2022

nonn

a(n) <= 4 since any number can be written as a sum of 4 squares (Lagrange's theorem).

Sequence first differs from A063274, A225926 and A274459 at n = 32 since 32 is a powerful number, a prime power and a perfect power but neither a square nor a cube.

			a(1) = 1, a(4) = 1 (4 = 2^2), a(7) = 4 (7 = 2^2 + 1^2 + 1^2 + 1^2), a(8) = 1 (8 = 2^3), a(12) = 2 (12 = 2^3 + 2^2), a(17) = 2 (17 = 4^2 + 1^2), a(32) = 2 (32 = 4^2 + 4^2).

Cf. A002760, A063274, A225926, A274459, A002376, A002828, A000290, A000578.

lista(n) = {my(v = vector(n)); for(j = 2, 3, for(i = 2, sqrtnint(n, j), v[i^j] = 1)); v[1]=1; v[2]=2; for(i=3, #v, if(v[i]==0, v[i] = vecmin(vector(i\2, k, v[k] + v[i-k])))); v}

cp's OEIS Frontend

A274459 Least number of perfect powers that add up to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A225927 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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

C

A290397 Least number of nonprime squarefree numbers (A000469) that add up to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A354761 Least number of squares and cubes that add up to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI