A255131 -id:A255131 - cp's OEIS frontend

A278216 Number of children that node n has in the tree defined by the edge relation A255131(child) = parent, "the least squares beanstalk".

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

Offset: 0

Antti Karttunen, Nov 25 2016

nonn

			a(0) = 4 as 0 - A002828(0) = 0, 1 - A002828(1) = 0, 2 - A002828(2) = 0 and 3 - A002828(3) = 0. (But 4 - A002828(4) = 3.) Note that 0 is the only number which is its own child as 0 - A002828(0) = 0.

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

Cf. A002828, A255131, A276573.

Cf. A278490 (positions of zeros), A278489 (positions of nonzeros), A278491 (positions of 4's).

(define (A278216 n) (let loop ((s 0) (k (+ 4 n))) (if (< k n) s (loop (+ s (if (= n (A255131 k)) 1 0)) (- k 1)))))

a(n) = Sum_{i=0..4} [A002828(n+i) = i]. (Here [ ] is the Iverson bracket, giving as its result 1 only if A002828(n+i) is i, otherwise zero.)

A278489 Nonleaves in the tree defined by edge relation A255131(child) = parent, the least squares beanstalk.

Original entry on oeis.org

0, 3, 6, 8, 9, 11, 15, 16, 18, 19, 21, 24, 27, 30, 32, 35, 38, 39, 40, 41, 43, 45, 48, 50, 51, 53, 54, 56, 59, 63, 64, 66, 67, 70, 71, 72, 73, 74, 75, 78, 80, 81, 83, 85, 87, 88, 90, 91, 93, 95, 96, 99, 102, 104, 105, 107, 108, 111, 112, 114, 115, 117, 120, 123, 126, 128, 129, 130, 131, 134, 135, 136, 137, 138, 139, 143, 144

Offset: 0

Antti Karttunen, Nov 25 2016

nonn

Numbers n for which there exists at least one such integer k that k - A002828(k) = n, in other words, numbers n such that either A002828(1+n) is 1 or A002828(2+n) is 2 or A002828(3+n) is 3 or A002828(4+n) is 4, as the maximum value that A002828 may obtain is 4.

Indexing starts from zero, because a(0)=0 is a special case in this sequence.

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

Complement: A278490.
Positions of nonzeros in A278216.
Cf. A276573 (the infinite trunk of the tree, is a subsequence).
Cf. A278491 (another subsequence).
Cf. A002828, A255131.

A278490 Leaves in the tree defined by edge relation A255131(child) = parent, the least squares beanstalk.

Original entry on oeis.org

1, 2, 4, 5, 7, 10, 12, 13, 14, 17, 20, 22, 23, 25, 26, 28, 29, 31, 33, 34, 36, 37, 42, 44, 46, 47, 49, 52, 55, 57, 58, 60, 61, 62, 65, 68, 69, 76, 77, 79, 82, 84, 86, 89, 92, 94, 97, 98, 100, 101, 103, 106, 109, 110, 113, 116, 118, 119, 121, 122, 124, 125, 127, 132, 133, 140, 141, 142, 145, 148, 150, 153, 154, 156, 157

Offset: 1

Antti Karttunen, Nov 25 2016

nonn

Numbers n for which there are no solutions to k - A002828(k) = n for any k, in other words, numbers n such that (A002828(1+n) <> 1) and (A002828(2+n) <> 2) and (A002828(3+n) <> 3) and (A002828(4+n) <> 4), as the maximum value that A002828 may obtain is 4.

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

Complement: A278489.
Positions of zeros in A278216.
Cf. A278494 (primes in this sequence).

A278515 Number of steps required to iterate map k -> A255131(k) when starting from k = (A000196(n)+1)^2 before n is reached, or 0 if n is not reached.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 2, 0, 1, 0, 0, 2, 0, 0, 0, 1, 4, 0, 3, 0, 0, 2, 0, 0, 1, 0, 0, 4, 0, 0, 3, 0, 2, 0, 0, 1, 0, 0, 5, 0, 4, 0, 0, 3, 0, 2, 0, 0, 1, 0, 0, 5, 0, 4, 0, 0, 3, 0, 0, 2, 0, 0, 0, 1, 7, 0, 0, 6, 0, 0, 5, 0, 4, 0, 0, 3, 0, 0, 2, 0, 1, 0, 0, 7, 0, 6, 0, 0, 5, 0, 4, 0, 0, 3, 0, 0, 2, 0, 0, 1, 0, 0, 7, 0, 0, 6, 0, 0, 5, 0, 0, 0, 4, 0, 0, 3, 0, 2, 0, 0, 1

Offset: 0

Antti Karttunen, Nov 28 2016

nonn

			For n=15, we start iterating from the next larger square, (floor(sqrt(15))+1)^2 = 16, and in just a single step (16 - A002828(16) = 15) we land to n, so a(15) = 1.
For n=16, we start iterating from the next larger square, which is 25, and thus we have 25 -> A255131(25) = 24, 24 -> A255131(24) = 21, 21 -> A255131(21) = 18, 18 -> A255131(18) = 16, thus four steps were required to reach 16, and a(16) = 4.
For n=17, when we do the same iteration, we see that we will pass by it, thus a(17) = 0.

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

Cf. A000196, A000290, A002828, A255131.

Cf. A005563 (positions of ones), A276573 (of nonzero terms).

(define (A278515 n) (let* ((r (A000196 n)) (end (A000290 r))) (let loop ((k (A000290 (+ 1 r))) (s 0)) (cond ((= k n) s) ((<= k end) 0) (else (loop (A255131 k) (+ 1 s)))))))

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

A236840 n minus number of runs in the binary expansion of n: a(n) = n - A005811(n).

Original entry on oeis.org

0, 0, 0, 2, 2, 2, 4, 6, 6, 6, 6, 8, 10, 10, 12, 14, 14, 14, 14, 16, 16, 16, 18, 20, 22, 22, 22, 24, 26, 26, 28, 30, 30, 30, 30, 32, 32, 32, 34, 36, 36, 36, 36, 38, 40, 40, 42, 44, 46, 46, 46, 48, 48, 48, 50, 52, 54, 54, 54, 56, 58, 58, 60, 62, 62, 62, 62, 64, 64, 64

Offset: 0

Antti Karttunen, Apr 18 2014

All terms are even. Used by the "number-of-runs beanstalk" sequence A255056 and many of its associated sequences.

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

Cf. A091067 (the positions of records), A106836 (run lengths).
Cf. A255070 (terms divided by 2).
Cf. A005811, A000120, A003188.
Cf. A255056, A255066, A255061, A255062, A255071, A255072, A255058, A255327.
Other subtracting maps: A011371, A178503, A219641, A219651, A227190, A227191, A237449, A244320, A244234, A255131.

A236840 := proc(n) local i, b; if n=0 then 0 else b := convert(n, base, 2); select(i -> (b[i-1]<>b[i]), [$2..nops(b)]); n-1-nops(%) fi end: seq(A236840(i), i=0..69); # Peter Luschny, Apr 19 2014

a[n_] := n - Length@ Split[IntegerDigits[n, 2]]; a[0] = 0; Array[a, 100, 0] (* Amiram Eldar, Jul 16 2023 *)

Scheme
```
(define (A236840 n)  (- n (A005811 n)))
```

a(n) = n - A005811(n) = n - A000120(A003188(n)).

a(n) = 2*A255070(n).

A260731 a(n) = Number of steps to reach 0 starting from x=n and using the iterated process: x -> x - A002828(x), where A002828(x) = the least number of squares that add up to x.

Original entry on oeis.org

0, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 8, 8, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 16, 16, 17, 17, 17, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 25, 26, 26, 27, 27, 28, 28, 28, 29, 29, 29, 30, 31, 31, 31, 32, 32, 32, 32, 33, 33, 34, 34, 34, 35, 35, 35, 36, 36, 37, 37, 38

Offset: 0

Antti Karttunen, Aug 12 2015

nonn

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

Cf. A002828, A255131, A260732, A260733, A260734.
Left inverse of A276573, A278517 and A278519. A278518(n) gives the number of times n occurs (run lengths).
Cf. also A261221.

A002828[n_] := Which[n == 0, 0, SquaresR[1, n] > 0, 1, SquaresR[2, n] > 0, 2, SquaresR[3, n] > 0, 3, True, 4]; a[0] = 0; a[n_] := a[n] = 1 + a[n - A002828[n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Nov 14 2016 *)

a(0) = 0; for >= 1, a(n) = 1 + A260731(A255131(n)).
From Antti Karttunen, Nov 28 2016: (Start)
For all n >= 0, a(A278517(n)) = a(A278519(n)) = a(A276573(n)) = n.
(End)

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

cp's OEIS Frontend

A278216 Number of children that node n has in the tree defined by the edge relation A255131(child) = parent, "the least squares beanstalk".

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Scheme

Formula

A278489 Nonleaves in the tree defined by edge relation A255131(child) = parent, the least squares beanstalk.

Views

Author

Keywords

Comments

Links

Crossrefs

A278490 Leaves in the tree defined by edge relation A255131(child) = parent, the least squares beanstalk.

Views

Author

Keywords

Comments

Links

Crossrefs

A278515 Number of steps required to iterate map k -> A255131(k) when starting from k = (A000196(n)+1)^2 before n is reached, or 0 if n is not reached.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Scheme

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

A236840 n minus number of runs in the binary expansion of n: a(n) = n - A005811(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Scheme

Formula

A260731 a(n) = Number of steps to reach 0 starting from x=n and using the iterated process: x -> x - A002828(x), where A002828(x) = the least number of squares that add up to x.

Views

Author

Keywords

Links

Crossrefs