A006892 -id:A006892 - cp's OEIS frontend

A053610 Number of positive squares needed to sum to n using the greedy algorithm.

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

Offset: 1

Jud McCranie, Mar 19 2000

nonn

Define f(n) = n - x^2 where (x+1)^2 > n >= x^2. a(n) = number of iterations in f(...f(f(n))...) to reach 0.
a(n) = 1 iff n is a perfect square.
Also sum of digits when writing n in base where place values are squares, cf. A007961. - Reinhard Zumkeller, May 08 2011
The sequence could have started with a(0)=0. - Thomas Ordowski, Jul 12 2014
The sequence is not bounded, see A006892. - Thomas Ordowski, Jul 13 2014

			7=4+1+1+1, so 7 requires 4 squares using the greedy algorithm, so a(7)=4.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A006892 (positions of records), A055401, A007961.

Cf. A000196, A000290, A057945 (summing triangular numbers).

a053610 n = s n $ reverse $ takeWhile (<= n) $ tail a000290_list where
  s _ []                 = 0
  s m (x:xs) | x > m     = s m xs
             | otherwise = m' + s r xs where (m',r) = divMod m x
-- Reinhard Zumkeller, May 08 2011

A053610 := proc(n)
    local a,x;
    a := 0 ;
    x := n ;
    while x > 0 do
        x := x-A048760(x) ;
        a := a+1 ;
    end do:
    a ;
end proc: # R. J. Mathar, May 13 2016

f[n_] := (n - Floor[Sqrt[n]]^2); g[n_] := (m = n; c = 1; While[a = f[m]; a != 0, c++; m = a]; c); Table[ g[n], {n, 1, 105}]

A053610(n,c=1)=while(n-=sqrtint(n)^2,c++);c \\ M. F. Hasler, Dec 04 2008

from math import isqrt
def A053610(n):
    c = 0
    while n:
        n -= isqrt(n)**2
        c += 1
    return c # Chai Wah Wu, Aug 01 2023

a(n) = A007953(A007961(n)). - Henry Bottomley, Jun 01 2000
a(n) = a(n - floor(sqrt(n))^2) + 1 = a(A053186(n)) + 1 [with a(0) = 0]. - Henry Bottomley, May 16 2000
A053610 = A002828 + A062535. - M. F. Hasler, Dec 04 2008

A053630 Pythagorean spiral: a(n-1), a(n)-1 and a(n) are sides of a right triangle.

Original entry on oeis.org

3, 5, 13, 85, 3613, 6526885, 21300113901613, 226847426110843688722000885, 25729877366557343481074291996721923093306518970391613

Offset: 1

Henry Bottomley, Mar 21 2000

Least prime factors of a(n): 3, 5, 13, 5, 3613, 5, 233, 5, 3169, 5, 101, 5, 29, 5, 695838629, 5, 1217, 5, 2557, 5, 101, 5, 769, 5. - Zak Seidov, Nov 11 2013

			a(3)=13 because 5,12,13 is a Pythagorean triple and a(2)=5.

R. Gelca and T. Andreescu, Putnam and Beyond, Springer 2007, p. 121.

Steven Finch, Exercises in Iterational Asymptotics, arXiv:2411.16062 [math.NT], 2024. See p. 10.
Miguel-Ángel Pérez García-Ortega, Capitulo 5. Catetos, El Libro de las Ternas Pitagóricas.

Cf. A000058, A001844, A006892.
See also A018928, A180313 and A239381 for similar sequences with a(n) a leg and a(n+1) the hypotenuse of a Pythagorean triangle.
Cf. A077125, A117191 (4^(1/Pi)).

A:= proc(n) option remember; (procname(n-1)^2+1)/2 end proc: A(1):= 3:
seq(A(n),n=1..10); # Robert Israel, Jul 14 2014

NestList[(#^2+1)/2&,3,10] (* Harvey P. Dale, Sep 15 2011 *)

{a(n) = if( n>1, (a(n-1)^2 + 1) / 2, 3)}; /* Michael Somos, May 15 2011 */

a(1) = 3, a(n) = (a(n-1)^2 + 1)/2 for n > 1.
a(n) = 2*A000058(n)-1 = A053631(n)+1 = floor(2 * 1.597910218031873...^(2^n)). Constructing the spiral as a sequence of triangles with one vertex at the origin, then for large n the other vertices are close to lying on the doubly logarithmic spiral r = 2*2.228918357655...^(1.5546822754821...^theta) where theta(n) = n*Pi/2 - 1.215918200344... and 1.5546822754821... = 4^(1/Pi).
a(1) = 3, a(n+1) = (1/4)*((a(n)-1)^2 + (a(n)+1)^2). - Amarnath Murthy, Aug 17 2005
a(n)^2 - (a(n)-1)^2 = a(n-1)^2, so 2*a(n)-1 = a(n-1)^2 (see the first formula). - Thomas Ordowski, Jul 13 2014
a(n) = (A006892(n+2) + 3)/2. - Thomas Ordowski, Jul 14 2014
a(n)^2 = A006892(n+3) + 2. - Thomas Ordowski, Jul 19 2014

Corrected and extended by James Sellers, Mar 22 2000

A055402 Least number represented as the sum of n cubes with greedy algorithm.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 15, 23, 50, 114, 330, 1330, 10591, 215970, 19464802, 16542386125, 409477218238718, 1594640520554911022654, 12254971660196485116306102211582, 8256321288165573196207266557193504883194549246

Offset: 1

Henry Bottomley, May 16 2000

nonn

			a(11) = 114 = 64 + 27 + 8 + 8 + 1 + 1 + 1 + 1 + 1 + 1 + 1.

Rick L. Shepherd, Table of n, a(n) for n = 1..28

Cf. A006892, A055401.

{default(realprecision, 255); v = []; n = 1;
while(n < 29,
  if(n < 8,
    a = n, a = v[n-1] + ceil(sqrt(v[n-1]/3 + 1/4) - 1/2)^3);
  v = concat(v, a);
  write("b055402.txt", n, " ", v[n]); n++)}
\\ Rick L. Shepherd, Jan 30 2014

a(n) = a(n-1) + ceiling(sqrt(a(n-1)/3 + 1/4) - 1/2)^3 for n >= 2.

More terms from Vladeta Jovovic, Jul 03 2001

A025486 Least k with A025485(k) = n.

Original entry on oeis.org

0, 3, 5, 10, 26, 170, 7226, 13053770, 42600227803226, 453694852221687377444001770, 51459754733114686962148583993443846186613037940783226

Offset: 0

David W. Wilson

nonn

For n >= 4, a(n) = a(n-1)^2/4+1.

Conjecture: a(n) = A006892(n+1)+3 for n >= 3. - R. J. Mathar, Apr 23 2007

Title corrected and missing a(1)=3 inserted by Sean A. Irvine, Aug 31 2019

A262123 a(1) + a(2) + ... + a(n) is the representation as a sum of n squares of the smallest integer needing n squares (using the greedy algorithm).

Original entry on oeis.org

1, 1, 1, 4, 16, 144, 7056, 13046544, 42600214749456, 453694852221644777216198544, 51459754733114686962148583539748993964925660496781456

Offset: 1

Robert FERREOL, Sep 11 2015

nonn

			23 =16+4+1+1+1 is the first number to need 5 squares for its greedy decomposition, so a(1)=1,a(2)=1,a(3)=1,a(4)=4,a(5)=16.

E. Lemoine, Décomposition d'un nombre entier N en ses puissances nièmes maxima, C. R. Acad. Sci. Paris, Vol. 95, pp. 719-722, 1882.

Cf. A006892.

a:=n->if n=1 then 1 else s:=add(a(k),k=1..n-1); floor((s+1)/2)^2 fi;

a[1] = 1; a[n_] := a[n] = Floor[(Total[Array[a, n-1]]+1)/2]^2; Array[a, 11] (* Jean-François Alcover, Oct 05 2015 *)

a(n) = if(n<4, 1,if(n==4, 4,(a(n-1)/2 + sqrtint(a(n-1)))^2));
vector(12, n, a(n)) \\ Altug Alkan, Oct 04 2015

def list_a(n):
    list=[1,1,1,4];root=2;length=4
    while length

a(1)=1; for n>1, if s = a(1)+a(2)+...+a(n-1) then a(n+1) = floor((s+1)/2)^2.
a(1)+...+a(n) = A006892(n).
a(1)=a(2)=a(3)=1, a(4)=4; for n>=4, a(n+1) = ( a(n)/2+sqrt(a(n)) )^2.

A296840 The smallest positive integer whose greedy representation as a sum of 3-smooth numbers (A003586) requires n terms.

Original entry on oeis.org

1, 5, 23, 185, 1721, 15545, 277689, 5586105, 113081529, 2289863865, 46369706169, 986739675321, 26376728842425, 711906436354233, 19221208539173049, 518972365315281081, 22132599848083154505, 944314039112845753929, 40290722114409383329353

Offset: 1

David Eppstein, Dec 21 2017

nonn

			For n = 4, 185 = 162 + 18 + 4 + 1 requires four terms in its greedy representation even though it has the shorter non-greedy representation 185 = 144 + 32 + 9.

David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.

Cf. A018899 (numbers requiring n terms in non-greedy representations as sums of A003586), A006892 and A066352 (sequences describing greedy representations as sums of squares and of primes respectively).

With[{nn = 19}, Block[{s = Sort@ Flatten@ Table[2^a * 3^b, {a, 0, Log[2, #]}, {b, 0, Log[3, #/2^a]}] &[10^Floor[8 nn/5]], t}, t = Transpose@ {Most@ s, Differences@ s}; Fold[Append[#1, Function[{a, n}, Last[a] + SelectFirst[t, Last[#] > Last@ a &][[1]]][#1, #2]] &, {1}, Range[2, nn]]]] (* Michael De Vlieger, Dec 22 2017 *)

a(n) is a(n-1) plus the smallest 3-smooth number s whose next successive 3-smooth number is greater than s + a(n-1). For instance, a(3) = 23 = 5 + 18, where a(2) = 5 is the predecessor of 23 in the sequence and where the first gap bigger than 5 among the 3-smooth numbers is the one from 18 to 24.

cp's OEIS Frontend

A053610 Number of positive squares needed to sum to n using the greedy algorithm.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A053630 Pythagorean spiral: a(n-1), a(n)-1 and a(n) are sides of a right triangle.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A055402 Least number represented as the sum of n cubes with greedy algorithm.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A025486 Least k with A025485(k) = n.

Views

Author

Keywords

Formula

Extensions

A262123 a(1) + a(2) + ... + a(n) is the representation as a sum of n squares of the smallest integer needing n squares (using the greedy algorithm).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A296840 The smallest positive integer whose greedy representation as a sum of 3-smooth numbers (A003586) requires n terms.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula