A260731 -id:A260731 - cp's OEIS frontend

A278518 First differences of A278517; run lengths in A260731.

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

Offset: 0

Antti Karttunen, Nov 28 2016

nonn

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

Cf. A260731, A278516, A278517, A278519, A278521, A278522.

(define (A278518 n) (- (A278517 (+ 1 n)) (A278517 n)))

a(n) = A278517(1+n) - A278517(n).
a(n) = 1 + (A278519(n) - A278517(n)).
a(n) = 1 + A278521(n) + A278522(n).

A278517 a(n) = smallest k for which A260731(k) = n.

Original entry on oeis.org

0, 1, 4, 8, 9, 12, 16, 18, 20, 24, 25, 29, 32, 34, 36, 40, 43, 45, 48, 49, 52, 56, 58, 61, 64, 67, 70, 72, 74, 77, 80, 81, 84, 88, 90, 93, 96, 98, 100, 104, 106, 109, 113, 116, 120, 121, 125, 128, 130, 133, 136, 139, 142, 144, 146, 148, 152, 155, 157, 160, 162, 164, 168, 169, 172, 176, 178, 180, 184, 187, 190, 193, 196, 200

Offset: 0

Antti Karttunen, Nov 28 2016

nonn

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

Cf. A260731 (a left inverse), A278518 (first differences), A278519, A278521.

Cf. also A002828, A276573.

For all n >= 0, A260731(a(n)) = n.

A278519 a(n) = largest k for which A260731(k) = n.

Original entry on oeis.org

0, 3, 7, 8, 11, 15, 17, 19, 23, 24, 28, 31, 33, 35, 39, 42, 44, 47, 48, 51, 55, 57, 60, 63, 66, 69, 71, 73, 76, 79, 80, 83, 87, 89, 92, 95, 97, 99, 103, 105, 108, 112, 115, 119, 120, 124, 127, 129, 132, 135, 138, 141, 143, 145, 147, 151, 154, 156, 159, 161, 163, 167, 168, 171, 175, 177, 179, 183, 186, 189, 192, 195, 199, 201

Offset: 0

Antti Karttunen, Nov 28 2016

nonn

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

Cf. A260731 (a left inverse), A278517, A278518 (first differences, after its initial 1), A278522.

(define (A278519 n) (if (zero? n) n (+ -1 (A278517 (+ 1 n)))))

a(0) = 0; for n > 0, a(n) = A278517(1+n)-1.

For all n >= 0, A260731(a(n)) = n.

A002828 Least number of squares that add up to n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

Lagrange's "Four Squares theorem" states that a(n) <= 4.
It is easy to show that this is also the least number of squares that add up to n^3.
a(n) is the number of iterations in f(...f(f(n))...) to reach 0, where f(n) = A262678(n) = n - A262689(n)^2. Allows computation of this sequence without Lagrange's theorem. - Antti Karttunen, Sep 09 2016
It is also easy to show that a(k^2*n) = a(n) for k > 0: Clearly a(k^2*n) <= a(n) but for all 4 cases of a(n) there is no k which would result in a(k^2*n) < a(n). - Peter Schorn, Sep 06 2021

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

Alois P. Heinz, Table of n, a(n) for n = 0..20000 (first 1001 terms from T. D. Noe with corrections from Michel Marcus)
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
N. J. A. Sloane, Transforms.
Eric Weisstein's World of Mathematics, Square Number.

Cf. A000290, A000415, A000419, A002376, A004215, A000378, A001481.

Cf. A010052, A025426, A025427, A053610, A062535, A072401, A229062, A255131, A260728, A260731, A260734, A262678, A262689, A262690, A276573.

a002828 0 = 0  -- confessedly  /= 1, as sum [] == 0
a002828 n | a010052 n == 1 = 1
          | a025426 n > 0 = 2 | a025427 n > 0 = 3 | otherwise = 4
-- Reinhard Zumkeller, Feb 26 2015

with(transforms);
sq:=[seq(n^2, n=1..20)];
LAGRANGE(sq,4,120);
# alternative:
f:= proc(n) local F,x;
   if issqr(n) then return 1 fi;
   if nops(select(t -> t[1] mod 4 = 3 and t[2]::odd, ifactors(n)[2])) = 0 then return 2 fi;
   x:= n/4^floor(padic:-ordp(n,2)/2);
   if x mod 8 = 7 then 4 else 3 fi
end proc:
0, seq(f(n),n=1..200); # Robert Israel, Jun 14 2016
# next Maple program:
b:= proc(n, i) option remember; convert(series(`if`(n=0, 1, `if`(i<1, 0,
      b(n, i-1)+(s-> `if`(s>n, 0, x*b(n-s, i)))(i^2))), x, 5), polynom)
    end:
a:= n-> ldegree(b(n, isqrt(n))):
seq(a(n), n=0..105);  # Alois P. Heinz, Oct 30 2021

SquareCnt[n_] := If[SquaresR[1, n] > 0, 1, If[SquaresR[2, n] > 0, 2, If[SquaresR[3, n] > 0, 3, 4]]]; Table[SquareCnt[n], {n, 150}] (* T. D. Noe, Apr 01 2011 *)
sc[n_]:=Module[{s=SquaresR[Range[4],n]},If[First[s]>0,1,Length[ First[ Split[ s]]]+1]]; Join[{0},Array[sc,110]] (* Harvey P. Dale, May 21 2014 *)

istwo(n:int)=my(f);if(n<3,return(n>=0););f=factor(n>>valuation(n, 2)); for(i=1,#f[,1],if(bitand(f[i,2],1)==1&&bitand(f[i,1],3)==3, return(0)));1
isthree(n:int)=my(tmp=valuation(n,2));bitand(tmp,1)||bitand(n>>tmp,7)!=7
a(n)=if(isthree(n), if(issquare(n), !!n, 3-istwo(n)), 4) \\ Charles R Greathouse IV, Jul 19 2011, revised Mar 17 2022

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

from sympy.core.power import isqrt
def A002828(n):
    dp = [-1] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        S = []
        r = isqrt(i)
        for j in range(1, r + 1):
            S.append(1 + dp[i - (j**2)])
        dp[i] = min(S)
    return dp[-1] # Darío Clavijo, Apr 21 2025

;; The first one follows Charles R Greathouse IV's PARI-code above:
(define (A002828 n) (cond ((zero? n) n) ((= 1 (A010052 n)) 1) ((= 1 (A229062 n)) 2) (else (+ 3 (A072401 n)))))
(define (A229062 n) (- 1 (A000035 (A260728 n))))
;; We can also compute this without relying on Lagrange's theorem. The following recursion-formula should be used together with the second Scheme-implementation of A262689 given in the Program section that entry:
(definec (A002828 n) (if (zero? n) n (+ 1 (A002828 (- n (A000290 (A262689 n)))))))
;; Antti Karttunen, Sep 09 2016

From Antti Karttunen, Sep 09 2016: (Start)
a(0) = 0; and for n >= 1, if A010052(n) = 1 [when n is a square], a(n) = 1, otherwise, if A229062(n)=1, then a(n) = 2, otherwise a(n) = 3 + A072401(n). [After Charles R Greathouse IV's PARI program.]
a(0) = 0; for n >= 1, a(n) = 1 + a(n - A262689(n)^2), (see comments).
a(n) = A053610(n) - A062535(n).
(End)

More terms from Arlin Anderson (starship1(AT)gmail.com)

A276573 The infinite trunk of least squares beanstalk: The only infinite sequence such that a(0) = 0 and a(n-1) = a(n) - least number of squares (A002828) that sum to a(n).

Original entry on oeis.org

0, 3, 6, 8, 11, 15, 16, 18, 21, 24, 27, 30, 32, 35, 38, 40, 43, 45, 48, 51, 53, 56, 59, 63, 64, 67, 70, 72, 75, 78, 80, 83, 85, 88, 90, 93, 96, 99, 102, 105, 108, 112, 115, 117, 120, 123, 126, 128, 131, 134, 136, 139, 143, 144, 147, 149, 152, 155, 158, 160, 162, 165, 168, 171, 173, 176, 179, 183, 186, 189, 192, 195

Offset: 0

Antti Karttunen, Sep 07 2016

nonn

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

Cf. A002828, A005563, A255131, A260731, A260733, A262689, A276572, A276574, A276575 (first differences), A277016 (squares present), A277015 (their square roots), A277888 (primes), A278486 (numbers one more than a prime), A278265, A278487, A278488, A278491 (another subsequence), A278497, A278498, A278499, A278513, A278516, A278517, A278518, A278519, A278521, A278522.
Cf. A277890 & A277891 (number of even and odd terms in each range. The latter seem to be slightly more numerous), A277889.
Positions of nonzero terms in A278515.
Subsequence of A278489, no common terms with A278490.
Cf. also A179016, A259934, A276583, A276613, A276623 for similar constructions.

(define (A276573 n) (A276574 (A276572 n)))

a(n) = A276574(A276572(n)).
Other identities and observations. For all n >= 0:
A260731(a(n)) = n.
a(A260733(n+1)) = A005563(n).
A278517(n) <= a(n) <= A278519(n).
A010873(a(n)) = A278499(n). [Terms reduced modulo 4.]
A010877(a(n)) = A278488(n). [modulo 8.]
A046523(a(n)) = A278497(n). [Least number with the same prime signature.]
A008683(a(n)) = A278513(n).
A065338(a(n)) = A278498(n).
A278509(a(n)) = A278265(n).
A278216(a(n)) = A278516(n). [Number of children the n-th node of the trunk has.]

Definition clarified and more identities added to the Formula section by Antti Karttunen, Nov 28 2016

A255131 n minus the least number of squares that add up to n: a(n) = n - A002828(n).

Original entry on oeis.org

0, 0, 0, 0, 3, 3, 3, 3, 6, 8, 8, 8, 9, 11, 11, 11, 15, 15, 16, 16, 18, 18, 19, 19, 21, 24, 24, 24, 24, 27, 27, 27, 30, 30, 32, 32, 35, 35, 35, 35, 38, 39, 39, 40, 41, 43, 43, 43, 45, 48, 48, 48, 50, 51, 51, 51, 53, 54, 56, 56, 56, 59, 59, 59, 63, 63, 63, 64, 66, 66, 67, 67, 70, 71, 72, 72, 73, 74, 75, 75, 78, 80, 80, 80, 81

Offset: 0

Antti Karttunen, Feb 24 2015

nonn

The associated beanstalk-sequence starts from a(0) as: 0, 3, 6, 8, 11, 15, 16, 18, 21, ... (A276573).

			a(0) = 0, because no squares are needed for an empty sum, and 0 - 0 = 0.
a(3) = 0, because 3 cannot be represented as a sum of less than three squares (1+1+1), and 3 - 3 = 0.
a(4) = 3, because 4 can be represented as a sum of just one square (namely 4 itself), and 4 - 1 = 3.

Robert Israel, Table of n, a(n) for n = 0..10000
Discussion on the SeqFan mailing list

Subsequence: A005563.
Cf. A000290, A002828, A062535, A260731, A260732, A260733, A260734, A262689, A276573.
Cf. also A011371, A236840, A260740.

f:= proc(n) local F, x;
   if issqr(n) then return n-1 fi;
   if nops(select(t -> t[1] mod 4 = 3 and t[2]::odd, ifactors(n)[2])) = 0 then return n-2 fi;
   x:= n/4^floor(padic:-ordp(n, 2)/2);
   if x mod 8 = 7 then n-4 else n-3 fi
end proc:
f(0):= 0:
map(f, [$0..100]); # Robert Israel, Mar 27 2018

{0}~Join~Table[n - (If[First@ # > 0, 1, Length[First@ Split@ #] + 1] &@ SquaresR[Range@ 4, n]), {n, 84}] (* Michael De Vlieger, Sep 08 2016, after Harvey P. Dale at A002828 *)

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

a(n) = A260740(n) + A062535(n).

A260733 a(n) = number of steps needed to reach zero when starting from k = (n^2)-1 and repeatedly applying the map that replaces k with k - A002828(k), where A002828(k) = the least number of squares that add up to k.

Original entry on oeis.org

0, 1, 3, 5, 9, 13, 18, 23, 30, 37, 44, 52, 62, 71, 81, 91, 104, 117, 131, 144, 159, 174, 190, 207, 224, 243, 262, 281, 301, 321, 343, 365, 388, 412, 437, 461, 487, 514, 539, 567, 596, 625, 654, 684, 715, 748, 781, 814, 848, 883, 918, 955, 991, 1030, 1067, 1105, 1145, 1187, 1227, 1269, 1311, 1354, 1396, 1441, 1486, 1531, 1579, 1624, 1673, 1723, 1773, 1821

Offset: 1

Antti Karttunen, Aug 12 2015

nonn

Antti Karttunen, Table of n, a(n) for n = 1..1024

One less than A260732.
Cf. A002828, A255131, A260731, A260734.
Cf. also A261223.

Table[Length[#] - 2 &@ NestWhileList[# - (If[First@ # > 0, 1, Length[ First@ Split@ #] + 1] &@ SquaresR[Range@ 4, #]) &, n^2, # != 0 &], {n, 72}] (* Michael De Vlieger, Sep 08 2016 *)

a(n) = A260731((n^2)-1).

a(n) = A260732(n)-1.

A260734 a(n) = number of steps needed to reach (n^2)-1 when starting from k = ((n+1)^2)-1 and repeatedly applying the map that replaces k with k - A002828(k), where A002828(k) = the least number of squares that add up to k.

Original entry on oeis.org

1, 2, 2, 4, 4, 5, 5, 7, 7, 7, 8, 10, 9, 10, 10, 13, 13, 14, 13, 15, 15, 16, 17, 17, 19, 19, 19, 20, 20, 22, 22, 23, 24, 25, 24, 26, 27, 25, 28, 29, 29, 29, 30, 31, 33, 33, 33, 34, 35, 35, 37, 36, 39, 37, 38, 40, 42, 40, 42, 42, 43, 42, 45, 45, 45, 48, 45, 49, 50, 50, 48, 53, 50, 51, 54, 52, 53, 54, 56, 56, 56, 58, 59, 59, 60, 60, 60, 61, 62, 62, 62, 65, 66, 66, 65

Offset: 1

Antti Karttunen, Aug 12 2015

nonn

Antti Karttunen, Table of n, a(n) for n = 1..1024

First differences of both A260732 and A260733.
Cf. A000290, A002828, A255131.
Cf. also A261224.

Table[Length[#] - 1 &@ NestWhileList[# - (If[First@ # > 0, 1, Length[ First@ Split@ #] + 1] &@ SquaresR[Range@ 4, #]) &, ((n + 1)^2) - 1, # != (n^2) - 1 &], {n, 95}] (* Michael De Vlieger, Sep 08 2016, after Harvey P. Dale at A002828 *)

a(n) = A260731(((n+1)^2)-1) - A260731((n^2)-1). [The definition.]
Equally, for all n >= 1:
a(n) = A260731((n+1)^2) - A260731(n^2).
a(n) = A260732(n+1) - A260732(n).
a(n) = A260733(n+1) - A260733(n).

A260732 a(n) = number of steps needed to reach zero when starting from k = n^2 and repeatedly applying the map that replaces k with k - {the least number of squares (A002828) that add up to k}.

Original entry on oeis.org

0, 1, 2, 4, 6, 10, 14, 19, 24, 31, 38, 45, 53, 63, 72, 82, 92, 105, 118, 132, 145, 160, 175, 191, 208, 225, 244, 263, 282, 302, 322, 344, 366, 389, 413, 438, 462, 488, 515, 540, 568, 597, 626, 655, 685, 716, 749, 782, 815, 849, 884, 919, 956, 992, 1031, 1068, 1106, 1146, 1188, 1228, 1270, 1312, 1355, 1397, 1442, 1487, 1532, 1580, 1625

Offset: 0

Antti Karttunen, Aug 12 2015

nonn

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

Partial sums of A260734.
Essentially one more than A260733.
Cf. A002828, A260731.
Cf. also A261222.

Table[Length[#] - 1 &@ NestWhileList[# - (If[First@ # > 0, 1, Length[ First@ Split@ #] + 1] &@ SquaresR[Range@ 4, #]) &, n^2, # != 0 &], {n, 0, 68}] (* Michael De Vlieger, Sep 08 2016, after Harvey P. Dale at A002828 *)

a(n) = A260731(n^2).

For all n >= 1: a(n) = 1 + A260733(n).

A261221 a(n) = number of steps to reach 0 when starting from k = n and repeatedly applying the map that replaces k with k - A053610(k), where A053610(k) = the number of positive squares needed to sum to k using the greedy algorithm.

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 26, 27, 27, 27, 28, 28, 28, 29

Offset: 0

Antti Karttunen, Aug 12 2015

nonn

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

Cf. A260740, A261222, A261223, A261224.

Cf. also A260731, A261226.

a(0) = 0; for n >= 1, a(n) = 1 + a(A260740(n)).

cp's OEIS Frontend

A278518 First differences of A278517; run lengths in A260731.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A278517 a(n) = smallest k for which A260731(k) = n.

Views

Author

Keywords

Links

Crossrefs

Formula

A278519 a(n) = largest k for which A260731(k) = n.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A002828 Least number of squares that add up to n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Scheme

Formula

Extensions

A276573 The infinite trunk of least squares beanstalk: The only infinite sequence such that a(0) = 0 and a(n-1) = a(n) - least number of squares (A002828) that sum to a(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

Extensions

A255131 n minus the least number of squares that add up to n: a(n) = n - A002828(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A260733 a(n) = number of steps needed to reach zero when starting from k = (n^2)-1 and repeatedly applying the map that replaces k with k - A002828(k), where A002828(k) = the least number of squares that add up to k.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A260734 a(n) = number of steps needed to reach (n^2)-1 when starting from k = ((n+1)^2)-1 and repeatedly applying the map that replaces k with k - A002828(k), where A002828(k) = the least number of squares that add up to k.

Views

Author

Keywords

Links