A053610 -id:A053610 - cp's OEIS frontend

A265744 a(n) is the number of Pell numbers (A000129) needed to sum to n using the greedy algorithm (A317204).

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

Offset: 0

Antti Karttunen, Dec 17 2015

a(0) = 0, because no numbers are needed to form an empty sum, which is zero.

It would be nice to know for sure whether this sequence also gives the least number of Pell numbers that add to n, i.e., that there cannot be even better nongreedy solutions.

A. F. Horadam, Zeckendorf representations of positive and negative integers by Pell numbers, Applications of Fibonacci Numbers, Springer, Dordrecht, 1993, pp. 305-316.

Antti Karttunen, Table of n, a(n) for n = 0..13860
L. Carlitz, Richard Scoville, and V. E. Hoggatt, Jr., Pellian Representations, The Fibonacci Quarterly, Vol. 10, No. 5 (1972), pp. 449-488.

Cf. A000129, A007953, A317204.
Cf. also A014420, A053610, A265404, A265743, A265745.
Similar sequences: A007895, A116543, A278043.

pell[1] = 1; pell[2] = 2; pell[n_] := pell[n] = 2*pell[n - 1] + pell[n - 2]; a[n_] := Module[{s = {}, m = n, k}, While[m > 0, k = 1; While[pell[k] <= m, k++]; k--; AppendTo[s, k]; m -= pell[k]; k = 1]; Plus @@ IntegerDigits[Total[3^(s - 1)], 3]]; Array[a, 100, 0] (* Amiram Eldar, Mar 12 2022 *)

a(n) = A007953(A317204(n)). - Amiram Eldar, Mar 12 2022

A006892 Representation as a sum of squares requires n squares with greedy algorithm.

Original entry on oeis.org

1, 2, 3, 7, 23, 167, 7223, 13053767, 42600227803223, 453694852221687377444001767, 51459754733114686962148583993443846186613037940783223

Offset: 1

Jeffrey Shallit

nonn

Of course Lagrange's theorem tells us that any positive integer can be written as a sum of at most four squares (cf. A004215).

Records in A053610. - Hugo van der Sanden, Jun 24 2015

			Here is why a(5) = 23: start with 23, subtract largest square <= 23, which is 16, getting 7.
Now subtract largest square <= 7, which is 4, getting 3.
Now subtract largest square <= 3, which is 1, getting 2.
Now subtract largest square <= 2, which is 1, getting 1.
Now subtract largest square <= 1, which is 1, getting 0.
Thus 23 = 16+4+1+1+1.
It took 5 steps to get to 0, and 23 is the smallest number which takes 5 steps. - _N. J. A. Sloane_, Jan 29 2014

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Rick L. Shepherd, Table of n, a(n) for n = 1..15
Art of Problem Solving, 2010 AMC 10A Problems/Problem 25 [From _Rick L. Shepherd_, Jan 28 2014]
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 (then next pages).
E. Lemoine, Sur la décomposition d'un nombre en ses carrés maxima, Assoc. Française pour L'Avancement des Sciences (1896), 73-77.

Cf. A004215, A053610.

a(n) = if (n <= 3, n , ((a(n-1)+3)/2)^2 - 2) \\ Michel Marcus, May 25 2013

For n >= 4, a(n) = a(n-1) + ((a(n-1)+1)/2)^2. - Joe K. Crump (joecr(AT)carolina.rr.com), Apr 16 2000
a(n) = n for n <= 3; for n > 3, a(n) = ((a(n-1)+3)/2)^2 - 2. - Arkadiusz Wesolowski, Mar 30 2013
a(n+2) = 2 * A053630(n) - 3. - Thomas Ordowski, Jul 14 2014
a(n+3) = A053630(n)^2 - 2. - Thomas Ordowski, Jul 19 2014

Four more terms from Rick L. Shepherd, Jan 27 2014

A062535 Don't be greedy! Difference between number of squares needed to sum to n using the greedy algorithm and using the best such sum.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 2, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0

Offset: 1

Henry Bottomley, Jun 25 2001

nonn

			a(32)=5-2=3 since 32 can be written greedily as 25+4+1+1+1 or efficiently as 16+16.

G. C. Greubel, Table of n, a(n) for n = 1..5000

Cf. A053610, A002828.

f[n_] := (n - Floor[Sqrt[n]]^2); a053610[n_] := (m = n; c = 1; While[a = f[m]; a != 0, c++; m = a]; c); SquareCnt[n_] := If[SquaresR[1, n] > 0, 1, If[SquaresR[2, n] > 0, 2, If[SquaresR[3, n] > 0, 3, 4]]]; (* a002828 *) Table[a053610[n] - SquareCnt[n], {n, 1, 100}] (* G. C. Greubel, Apr 18 2017 *)

from math import isqrt
from sympy import factorint
def A062535(n):
    c, k, f = 0, n, factorint(n).items()
    while k:
        k -= isqrt(k)**2
        c += 1
    if not any(e&1 for p,e in f): return c-1
    if all(p&3<3 or e&1^1 for p,e in f): return c-2
    return c-3-(((m:=(~n&n-1).bit_length())&1^1)&int((n>>m)&7==7)) # Chai Wah Wu, Aug 01 2023

a(n) = A053610(n) - A002828(n).

A265404 a(n) = number of Spironacci numbers (A078510) needed to sum to n using the greedy algorithm.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2

Offset: 0

Antti Karttunen, Dec 16 2015

nonn

a(0) = 0, because no numbers are needed to form an empty sum, which is zero.

First 2 occurs as a(17), first 3 at a(234), first 4 at a(3266).

			For n=17, the largest Spironacci number <= 17 is 16 (= A078510(22)). 17 - 16 = 1, which is A078510(1), thus 17 = A078510(22) + A078510(1), requiring only two such numbers for its sum, thus a(17) = 2.
For n=234, the largest Spironacci number <= 234 is 217 (= A078510(45)). 234-217 = 17 (whose decomposition is shown above), so 234 = A078510(45) + A078510(22) + A078510(1), thus a(234) = 3.

Antti Karttunen, Table of n, a(n) for n = 0..10132

Cf. A078510 (from its term a(7) onward gives also the positions of ones here).

Cf. also A007895, A053610, A265743, A265744, A265745.

A190321 Number of nonzero digits when writing n in base where place values are squares, cf. A007961.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 1, 2, 2, 2, 2, 3, 3, 3, 2, 1, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 1, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 3, 1, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 4, 1, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 3, 3, 4, 4, 2, 1, 2, 2, 2, 2

Offset: 0

Reinhard Zumkeller, May 08 2011

For n > 0: a(A000290(n)) = 1; for n > 1: a(A002522(n)) = 2;

a(n) <= A000196(n).

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

Cf. A190311, A053610.

a190321 n = g n $ reverse $ takeWhile (<= n) $ tail a000290_list where
  g _ []                 = 0
  g m (x:xs) | x > m     = g m xs
             | otherwise = signum m' + g r xs where (m',r) = divMod m x

A265743 a(n) = number of terms of A005187 needed to sum to n using the greedy algorithm.

Original entry on oeis.org

0, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 2, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 2, 3, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 2, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 1, 2, 3, 2, 2, 3, 4, 1, 1

Offset: 0

Antti Karttunen, Dec 17 2015

nonn

a(0) = 0, because no numbers are needed to form an empty sum, which is zero.

Antti Karttunen, Table of n, a(n) for n = 0..8192

Cf. A005187, A055938.

Cf. also A000120, A007895, A053610, A265404, A265744, A265745.

Other identities. For all n >= 1:

a(A005187(n)) = 1 and a(A055938(n)) > 1.

A276584 The infinite trunk of greedy squares beanstalk with reversed subsections.

Original entry on oeis.org

0, 3, 8, 6, 15, 11, 24, 21, 18, 35, 32, 27, 48, 43, 38, 63, 59, 56, 51, 80, 78, 74, 71, 66, 99, 95, 91, 88, 83, 120, 117, 114, 110, 107, 102, 143, 138, 135, 131, 128, 123, 168, 164, 161, 158, 154, 151, 146, 195, 192, 186, 183, 179, 176, 171, 224, 219, 213, 210, 206, 203, 198, 255, 251, 248, 242, 239, 235, 232, 227

Offset: 0

Antti Karttunen, Sep 07 2016 and Sep 09 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 0..9996

Cf. A000196, A000290, A010052, A053610, A260740, A276582, A276583.

(definec (A276584 n) (cond ((zero? n) n) ((= 1 n) 3) (else (let ((maybe_next (A260740 (A276584 (- n 1))))) (if (zero? (A010052 (+ 1 maybe_next))) maybe_next (+ -1 (A000290 (+ 2 (A000196 (+ 1 maybe_next))))))))))

a(0) = 0; a(1) = 3; for n > 1, if A260740(a(n-1))+1 is not a square, then a(n) = A260740(a(n-1)), otherwise a(n) = A000290(2+A000196(A260740(a(n-1)))) - 1.

A350674 Irregular table read by rows; the n-th row contains, in weakly decreasing order, the positive squares summing to n as obtained by the greedy algorithm.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 4, 4, 1, 4, 1, 1, 4, 1, 1, 1, 4, 4, 9, 9, 1, 9, 1, 1, 9, 1, 1, 1, 9, 4, 9, 4, 1, 9, 4, 1, 1, 16, 16, 1, 16, 1, 1, 16, 1, 1, 1, 16, 4, 16, 4, 1, 16, 4, 1, 1, 16, 4, 1, 1, 1, 16, 4, 4, 25, 25, 1, 25, 1, 1, 25, 1, 1, 1, 25, 4, 25, 4, 1, 25, 4, 1, 1

Offset: 1

Rémy Sigrist, Jan 10 2022

The n-th row has A053610(n) terms.

			The first rows are:
     1:    [1]
     2:    [1, 1]
     3:    [1, 1, 1]
     4:    [4]
     5:    [4, 1]
     6:    [4, 1, 1]
     7:    [4, 1, 1, 1]
     8:    [4, 4]
     9:    [9]
    10:    [9, 1]
    11:    [9, 1, 1]
    12:    [9, 1, 1, 1]
    13:    [9, 4]
    14:    [9, 4, 1]
    15:    [9, 4, 1, 1]
    16:    [16]

Andrew Howroyd, Table of n, a(n) for n = 1..1733 (rows 1..500)

Cf. A007961, A048760, A053610, A350698.

row(n,e=2) = { my (g=[], r); while (n, r=sqrtnint(n,e); n-=r^e; g=concat(g,[r^e])); g }

T(n, 1) = A048760(n).

T(n, A053610(n)) = A350698(n).

A063772 a(k^2 + i) = k + a(i) for k >= 0 and 0 <= i <= k * 2; a(0) = 0.

Original entry on oeis.org

0, 1, 2, 3, 2, 3, 4, 5, 4, 3, 4, 5, 6, 5, 6, 7, 4, 5, 6, 7, 6, 7, 8, 9, 8, 5, 6, 7, 8, 7, 8, 9, 10, 9, 8, 9, 6, 7, 8, 9, 8, 9, 10, 11, 10, 9, 10, 11, 12, 7, 8, 9, 10, 9, 10, 11, 12, 11, 10, 11, 12, 13, 12, 13, 8, 9, 10, 11, 10, 11, 12, 13, 12, 11, 12, 13, 14, 13, 14, 15, 12, 9, 10, 11, 12

Offset: 0

Reinhard Zumkeller, Aug 15 2001

a(n^2) = n (by definition).
First difference from A138554 is a(32) = 10 (5^2+2^2+1^2+1^2+1^2), A138554(32) = 8 (4^2+4^2). - Franklin T. Adams-Watters, Jun 25 2015
a(n) is the sum of the roots of the summands when n is expressed as a sum of squares using the greedy algorithm (as in A053610). - Franklin T. Adams-Watters, Jun 30 2015

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A053610, A138554.

a:= proc(n)  option remember;
      local k;
      k:= floor(sqrt(n));
      k + procname(n-k^2);
end proc:
a(0):= 0:
map(a, [$0..100]); # Robert Israel, Jun 30 2015

a[0] = 0; a[n_] := a[n] = With[{k = n // Sqrt // Floor}, k + a[n-k^2]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Mar 04 2019 *)

A112687 Numbers n that cannot be decomposed into the sum of at most 4 square numbers when using the following algorithm: Repeat the following 2 steps 4 times: 1-find the largest square s smaller than n; 2-n=n-s Numbers that can be decomposed yield final values of n=0. The sequence presented is of those numbers where n is not 0 when this algorithm ends.

Original entry on oeis.org

23, 32, 43, 48, 56, 61, 71, 76, 79, 88, 93, 96, 107, 112, 115, 119, 128, 133, 136, 140, 143, 151, 156, 159, 163, 166, 167, 176, 181, 184, 188, 191, 192, 203, 208, 211, 215, 218, 219, 224, 232, 237, 240, 244, 247, 248, 253, 263, 268, 271, 275, 278, 279, 284

Offset: 1

Luis F.B.A. Alexandre (lfbaa(AT)di.ubi.pt), Dec 31 2005

nonn

Found while writing a program to decompose integers as sums of four square numbers (following Lagrange's Four-Square Theorem).
Question: does the sum of the reciprocals of the numbers in this sequence converge? - J. Lowell, May 03 2014
Answer: this series is divergent. - Thomas Ordowski, May 22 2016
Numbers n such that A053610(n) > 4. - Thomas Ordowski, May 22 2016

			23 is the first number that cannot be decomposed because 16+4+1+1 falls short by one.

Enrique Pérez Herrero, Table of n, a(n) for n = 1..10000
E. J. Ionascu, Equilateral triangles in Z^4, arXiv:1209.0147 [math.NT], 2012-2013.
Eric Weisstein's World of Mathematics, Lagrange's Four-Square Theorem
Wikipedia, Lagrange's Four-Square Theorem

for n=1:312 a=n; i=1; while(i<5 & n~=0) j=1; while(j*j<=n) j=j+1; end; n=n-(j-1)*(j-1); i=i+1; end; if(n~=0) disp(a); end; end; % Luis F.B.A. Alexandre (lfbaa(AT)di.ubi.pt), Feb 08 2010

f1[x_]:=Floor[Sqrt[x]];
f2[x_]:=Floor[Sqrt[x-f1[x]^2]];
f3[x_]:=Floor[Sqrt[x-f1[x]^2-f2[x]^2]];
f4[x_]:=Floor[Sqrt[x-f1[x]^2-f2[x]^2-f3[x]^2]];
Err[n_]:=n-(f1[n]^2+f2[n]^2+f3[n]^2+f4[n]^2);
Select[Table[n,{n,0,5000}],Err[#]!=0&] (* Enrique Pérez Herrero, Dec 19 2013 *)

Included terms where the final value of n is larger than 1. The fact that some terms might be missing was noted by Alonso del Arte on 2010-02-07. Luis F.B.A. Alexandre (lfbaa(AT)di.ubi.pt), Feb 08 2010

cp's OEIS Frontend

A265744 a(n) is the number of Pell numbers (A000129) needed to sum to n using the greedy algorithm (A317204).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A006892 Representation as a sum of squares requires n squares with greedy algorithm.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A062535 Don't be greedy! Difference between number of squares needed to sum to n using the greedy algorithm and using the best such sum.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A265404 a(n) = number of Spironacci numbers (A078510) needed to sum to n using the greedy algorithm.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A190321 Number of nonzero digits when writing n in base where place values are squares, cf. A007961.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A265743 a(n) = number of terms of A005187 needed to sum to n using the greedy algorithm.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A276584 The infinite trunk of greedy squares beanstalk with reversed subsections.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A350674 Irregular table read by rows; the n-th row contains, in weakly decreasing order, the positive squares summing to n as obtained by the greedy algorithm.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI