A225926 -id:A225926

Search: a225926 -id:a225926

Displaying 1-4 of 4 results found.

page 1

A274459

Least number of perfect powers that add up to n.

+10
3

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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]

LINKS

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

EXAMPLE

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.

MATHEMATICA

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 *)

PROG

(PARI) 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

CROSSREFS

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

KEYWORD

nonn

AUTHOR

Sergio Pimentel, Jun 23 2016

EXTENSIONS

More terms from Michael De Vlieger, Jun 23 2016

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

STATUS

approved

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.

+10
1

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,12

COMMENTS

Nontrivial prime powers: A025475 except 1.

LINKS

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

EXAMPLE

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

PROG

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

}

CROSSREFS

Cf. A025475, A225926.

KEYWORD

nonn

AUTHOR

Alex Ratushnyak, May 21 2013

STATUS

approved

A290397

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

+10
0

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

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

EXAMPLE

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.

CROSSREFS

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

KEYWORD

nonn

AUTHOR

Ilya Gutkovskiy, Jul 29 2017

STATUS

approved

A354761

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

+10
0

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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.

LINKS

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

EXAMPLE

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

PROG

(PARI) 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}

CROSSREFS

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

KEYWORD

nonn

AUTHOR

Peter Schorn, Jun 06 2022

STATUS

approved

page 1

Search completed in 0.008 seconds