A000302 -id:A000302 - cp's OEIS frontend

A299924 Number of ways to write n^2 as x^2 + y^2 + z^2 + w^2 with x,y,z,w nonnegative integers such that x + 2y + 3z is a power of 4 (including 4^0 = 1).

1, 1, 1, 1, 3, 4, 1, 1, 2, 2, 1, 2, 1, 1, 3, 1, 1, 11, 4, 6, 7, 7, 8, 4, 4, 6, 14, 4, 6, 17, 10, 1, 10, 6, 10, 7, 4, 4, 16, 2, 3, 10, 2, 1, 9, 6, 3, 2, 1, 5, 2, 3, 7, 9, 3, 1, 6, 2, 3, 7, 1, 4, 4, 1, 3, 4, 3, 1, 13, 20

Offset: 1

Zhi-Wei Sun, Feb 21 2018

nonn

Conjecture: (i) a(n) > 0 for all n > 0, and a(n) = 1 only for n = 3, 7, 13, 49, 61, 4^k*m (k = 0,1,2,... and m = 1, 2, 11, 14, 17).
(ii) Let a,b,c,d be nonnegative integers with a >= b >= c >= d, b positive, and gcd(a,b,c,d) not divisible by 4. Then, any positive square can be written as x^2 + y^2 + z^2 + w^2 with x,y,z,w nonnegative integers such that a*x + b*y + c*z + d*w = 4^k for some k = 0,1,2,..., if and only if d = 0 and (a,b,c) is among the following ordered triples: (3,2,1), (2,1,0), (3,1,0), (4,2,0), (8,1,0), (15,1,0) and (16,2,0).
By Theorem 1.1(i) of arXiv:1701.05868, any positive square can be written as (4^k)^2 + x^2 + y^2 + z^2 with k,x,y,z nonnegative integers.
We have verified that a(n) > 0 for all n = 1..50000.

			a(1) = 1 since 1^2 = 1^2 + 0^2 + 0^2 + 0^2 with 1 + 2*0 + 3*0 = 4^0.
a(2) = 1 since 2^2 = 0^2 + 2^2 + 0^2 + 0^2 with 0 + 2*2 + 3*0 = 4.
a(3) = 1 since 3^2 = 2^2 + 1^2 + 0^2 + 2^2 with 2 + 2*1 + 3*0 = 4.
a(7) = 1 since 7^2 = 2^2 + 4^2 + 2^2 + 5^2 with 2 + 2*4 + 3*2 = 4^2.
a(11) = 1 since 11^2 = 2^2 + 1^2 + 4^2 + 10^2 with 2 + 2*1 + 4*3 = 4^2.
a(13) = 1 since 13^2 = 8^2 + 1^2 + 2^2 + 10^2 with 8 + 2*1 + 3*2 = 4^2.
a(14) = 1 since 14^2 = 4^2 + 6^2 + 0^2 + 12^2 with 4 + 2*6 + 3*0 = 4^2.
a(17) = 1 since 17^2 = 0^2 + 8^2 + 0^2 + 15^2 with 0 + 2*8 + 4*0 = 4^2.
a(49) = 1 since 49^2 = 22^2 + 3^2 + 12^2 + 42^2 with 22 + 2*3 + 3*12 = 4^3.
a(61) = 1 since 61^2 = 6^2 + 20^2 + 6^2 + 57^2 with 6 + 2*20 + 3*6 = 4^3.

Zhi-Wei Sun, Table of n, a(n) for n = 1..500
Zhi-Wei Sun, Refining Lagrange's four-square theorem, J. Number Theory 175(2017), 167-190.
Zhi-Wei Sun, Restricted sums of four squares, arXiv:1701.05868 [math.NT], 2017-2018.

Cf. A000118, A000302, A271518, A279612, A281976, A299825, A300219.

SQ[n_]:=SQ[n]=IntegerQ[Sqrt[n]];
Pow[n_]:=Pow[n]=IntegerQ[Log[4,n]];
Do[r=0;Do[If[SQ[n^2-x^2-y^2-z^2]&&Pow[x+2y+3z],r=r+1],{x,0,n},{y,0,Sqrt[n^2-x^2]},{z,0,Sqrt[n^2-x^2-y^2]}];Print[n," ",r],{n,1,70}]

A001024 Powers of 15.

Original entry on oeis.org

1, 15, 225, 3375, 50625, 759375, 11390625, 170859375, 2562890625, 38443359375, 576650390625, 8649755859375, 129746337890625, 1946195068359375, 29192926025390625, 437893890380859375, 6568408355712890625, 98526125335693359375, 1477891880035400390625, 22168378200531005859375, 332525673007965087890625

Offset: 0

N. J. A. Sloane

Same as Pisot sequences E(1, 15), L(1, 15), P(1, 15), T(1, 15). Essentially same as Pisot sequences E(15, 225), L(15, 225), P(15, 225), T(15, 225). See A008776 for definitions of Pisot sequences.
A000005(a(n)) = A000290(n+1). - Reinhard Zumkeller, Mar 04 2007
If X_1, X_2, ..., X_n is a partition of the set {1,2,...,2*n} into blocks of size 2 then, for n>=1, a(n) is equal to the number of functions f : {1,2,..., 2*n}->{1,2,3,4} such that for fixed y_1,y_2,...,y_n in {1,2,3,4} we have f(X_i)<>{y_i}, (i=1,2,...,n). - Milan Janjic, May 24 2007
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=1, a(n) equals the number of 15-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
Number of ways to assign truth values to n quaternary disjunctions connected by conjunctions such that the proposition is true. For example, a(2) = 225, since for the proposition (a v b v c v d) & (e v f v g v h) there are 225 assignments that make the proposition true. - Ori Milstein, Jan 26 2023

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

T. D. Noe, Table of n, a(n) for n = 0..100
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 279
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
Tanya Khovanova, Recursive Sequences
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Index entries for linear recurrences with constant coefficients, signature (15).

a(n) = A159991(n)/A000302(n). - Reinhard Zumkeller, May 02 2009

Row 6 of A329332.

[ 15^n: n in [0..20] ]; // Vincenzo Librandi, Nov 21 2010

[ n eq 1 select 1 else 15*Self(n-1): n in [1..21] ];

A001024:=-1/(-1+15*z); # Simon Plouffe in his 1992 dissertation

Table[15^n,{n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 15 2011 *)

a(n)=15^n \\ Charles R Greathouse IV, Sep 24 2015

G.f.: 1/(1-15x), e.g.f.: exp(15x)

a(n) = 15^n; a(n) = 15*a(n-1) with a(0)=1. - Vincenzo Librandi, Nov 21 2010

More terms from James Sellers, Sep 19 2000

A163493 Number of binary strings of length n which have the same number of 00 and 01 substrings.

Original entry on oeis.org

1, 2, 2, 3, 6, 9, 15, 30, 54, 97, 189, 360, 675, 1304, 2522, 4835, 9358, 18193, 35269, 68568, 133737, 260802, 509132, 995801, 1948931, 3816904, 7483636, 14683721, 28827798, 56637969, 111347879, 219019294, 431043814, 848764585, 1672056525, 3295390800, 6497536449

Offset: 0

Christopher Carl Heckman, Jul 29 2009

nonn

A variation of problem 11424 in the American Mathematical Monthly. Terms were brute-force calculated using Maple 10.
Proposed Problem 11610 in the Dec 2011 A.M.M.
From Gus Wiseman, Jul 27 2021: (Start)
Also the antidiagonal sums of the matrices counting integer compositions by length and alternating sum (A345197). So a(n) is the number of integer compositions of n + 1 of length (n - s + 3)/2, where s is the alternating sum of the composition. For example, the a(0) = 1 through a(6) = 7 compositions are:
  (1)  (2)   (3)   (4)    (5)     (6)     (7)
       (11)  (21)  (31)   (41)    (51)    (61)
                   (121)  (122)   (123)   (124)
                          (221)   (222)   (223)
                          (1112)  (321)   (322)
                          (1211)  (1122)  (421)
                                  (1221)  (1132)
                                  (2112)  (1231)
                                  (2211)  (2122)
                                          (2221)
                                          (3112)
                                          (3211)
                                          (11131)
                                          (12121)
                                          (13111)
For a bijection with the main (binary string) interpretation, take the run-lengths of each binary string of length n + 1 that satisfies the condition and starts with 1.
(End)

			1 + 2*x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 15*x^6 + 30*x^7 + 54*x^8 + 97*x^9 + ...
From _Gus Wiseman_, Jul 27 2021: (Start)
The a(0) = 1 though a(6) = 15 binary strings:
  ()  (0)  (1,0)  (0,0,1)  (0,0,1,0)  (0,0,1,1,0)  (0,0,0,1,0,1)
      (1)  (1,1)  (1,1,0)  (0,0,1,1)  (0,0,1,1,1)  (0,0,1,0,0,1)
                  (1,1,1)  (0,1,0,0)  (0,1,1,0,0)  (0,0,1,1,1,0)
                           (1,0,0,1)  (1,0,0,1,0)  (0,0,1,1,1,1)
                           (1,1,1,0)  (1,0,0,1,1)  (0,1,0,0,0,1)
                           (1,1,1,1)  (1,0,1,0,0)  (0,1,1,1,0,0)
                                      (1,1,0,0,1)  (1,0,0,1,1,0)
                                      (1,1,1,1,0)  (1,0,0,1,1,1)
                                      (1,1,1,1,1)  (1,0,1,1,0,0)
                                                   (1,1,0,0,1,0)
                                                   (1,1,0,0,1,1)
                                                   (1,1,0,1,0,0)
                                                   (1,1,1,0,0,1)
                                                   (1,1,1,1,1,0)
                                                   (1,1,1,1,1,1)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3328 (first 501 terms from R. H. Hardin)
Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, arXiv preprint arXiv:1112.6207 [math.CO], 2011. See subpages for rigorous derivations of g.f., recurrence, asymptotics for this sequence. [From _N. J. A. Sloane_, Apr 07 2012]
R. Stanley, Problem 11610, Amer. Math. Monthly, 118 (2011), 937; 120 (2013), 943-944.

Antidiagonal sums of the matrices A345197.
Row sums of A345907.
Taking diagonal instead of antidiagonal sums gives A345908.
A011782 counts compositions (or binary strings).
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000041, A000070, A000096, A000097, A000124, A000346, A007318, A008549, A025047, A131577, A238279.

with(combinat): count := proc(n) local S, matches, A, k, i; S := subsets(\{seq(i, i=1..n)\}): matches := 0: while not S[finished] do A := S[nextvalue](): k := 0: for i from 1 to n-1 do: if not (i in A) and not (i+1 in A) then k := k + 1: fi: if not (i in A) and (i+1 in A) then k := k - 1: fi: od: if (k = 0) then matches := matches + 1: fi: end do; return(matches); end proc:
# second Maple program:
b:= proc(n, l, t) option remember; `if`(n-abs(t)<0, 0, `if`(n=0, 1,
      add(b(n-1, i, t+`if`(l=0, (-1)^i, 0)), i=0..1)))
    end:
a:= n-> b(n, 1, 0):
seq(a(n), n=0..36);  # Alois P. Heinz, Mar 20 2024

a[0] = 1; a[n_] := Sum[Binomial[2*k - 1, k]*Binomial[n - 2*k, k] + Binomial[2*k, k]*Binomial[n - 2*k - 1, k], {k, 0, n/3}];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 28 2017, after Joel B. Lewis *)
Table[Length[Select[Tuples[{0,1},n],Count[Partition[#,2,1],{0,0}]==Count[Partition[#,2,1],{0,1}]&]],{n,0,10}] (* Gus Wiseman, Jul 27 2021 *)
a[0]:=1; a[n_]:=(1 + 3*HypergeometricPFQ[{1/2, 1-3*n/8, (1-n)/3, (2-n)/3, -n/3},{1, (1-n)/2, 1-n/2, -3*n/8}, -27])/2; Array[a,37,0] (* Stefano Spezia, Apr 26 2024 *)

from math import comb
def A163493(n): return 2+sum((x:=comb((k:=m<<1)-1,m)*comb(n-k,m))+(x*(n-3*m)<<1)//(n-k) for m in range(1,n//3+1)) if n else 1 # Chai Wah Wu, May 01 2024

G.f.: 1/2/(1-x) + (1+2*x)/2/sqrt((1-x)*(1-2*x)*(1+x+2*x^2)). - Richard Stanley, corrected Apr 29 2011
G.f.: (1 + sqrt( 1 + 4*x / ((1 - x) * (1 - 2*x) * (1 + x + 2*x^2)))) / (2*(1 - x)). - Michael Somos, Jan 30 2012
a(n) = sum( binomial(2*k-1, k)*binomial(n-2*k,k) + binomial(2*k, k)*binomial(n-2*k-1, k), k=0..floor(n/3)). - Joel B. Lewis, May 21 2011
Conjecture: -n*a(n) +(2+n)*a(n-1) +(3n-12)*a(n-2) +(12-n)*a(n-3) +(2n-18)*a(n-4)+(56-12n)*a(n-5) +(8n-40)*a(n-6)=0. - R. J. Mathar, Nov 28 2011
G.f. y = A(x) satisfies x = (1 - x) * (1 - 2*x) * (1 + x + 2*x^2) * y * (y * (1 - x) - 1). - Michael Somos, Jan 30 2012
Sequence a(n) satisfies 0 = a(n) * (n^2-2*n) + a(n-1) * (-3*n^2+8*n-2) + a(n-2) * (3*n^2-10*n+2) + a(n-3) * (-5*n^2+18*n-6) + a(n-4) * (8*n^2-34*n+22) + a(n-5) * (-4*n^2+20*n-16) except if n=1 or n=2. - Michael Somos, Jan 30 2012
a(n) = (1 + 3*hypergeom([1/2, 1-3*n/8, (1-n)/3, (2-n)/3, -n/3],[1, (1-n)/2, 1-n/2, -3*n/8],-27))/2 for n > 0. - Stefano Spezia, Apr 26 2024
a(n) ~ 2^n / sqrt(Pi*n). - Vaclav Kotesovec, Apr 26 2024

A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}.

Original entry on oeis.org

1, 0, 1, 2, 6, 10, 26, 42, 106, 170, 426, 682, 1706, 2730, 6826, 10922, 27306, 43690, 109226, 174762, 436906, 699050, 1747626, 2796202, 6990506, 11184810, 27962026, 44739242, 111848106, 178956970, 447392426, 715827882, 1789569706, 2863311530, 7158278826

Offset: 0

Emeric Deutsch, May 16 2001

Or, number of permutations with no fixed points avoiding 213 and 132.
Number of derangements of {1,2,...,n} having ascending runs consisting of consecutive integers. Example: a(4)=6 because we have 234/1, 34/12, 34/2/1, 4/123, 4/3/12, 4/3/2/1, the ascending runs being as indicated. - Emeric Deutsch, Dec 08 2004
Let c be twice the sequence A002450 interlaced with itself (from the second term), i.e., c = 2*(0, 1, 1, 5, 5, 21, 21, 85, 85, 341, 341, ...). Let d be powers of 4 interlaced with the zero sequence: d = (1, 0, 4, 0, 16, 0, 64, 0, 256, 0, ...). Then a(n+1) = c(n) + d(n). - Creighton Dement, May 09 2005
Inverse binomial transform of A094705 (0, 1, 4, 15). - Paul Curtz, Jun 15 2008
Equals row sums of triangle A177993. - Gary W. Adamson, May 16 2010
a(n-1) is also the number of order preserving partial isometries (of an n-chain) of fix 1 (fix of alpha equals the number of fixed points of alpha). - Abdullahi Umar, Dec 28 2010
a(n+1) <= A218553(n) is also the Moore lower bound on the order of a (5,n)-cage. - Jason Kimberley, Oct 31 2011
For n > 0, a(n) is the location of the n-th new number to make a first appearance in A087230. E.g., the 17th number to make its first appearance in A087230 is 18 and this occurs at A087230(43690) and a(17)=43690. - K D Pegrume, Jan 26 2022
Position in A002487 of 2 adjacent terms of A000045. E.g., 3/5 at 10, 5/8 at 26, 8/13 at 42, ... - Ed Pegg Jr, Dec 27 2022

			a(4)=6 because the only 132 and 213-avoiding permutations of {1,2,3,4} without fixed points are: 2341, 3412, 3421, 4123, 4312 and 4321.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
F. Al-Kharousi, R. Kehinde and A. Umar, Combinatorial results for certain semigroups of partial isometries of a finite chain, The Australasian Journal of Combinatorics, Volume 58 (3) (2014), 363-375.
J. Brillhart and P. Morton, A case study in mathematical research: the Golay-Rudin-Shapiro sequence, Amer. Math. Monthly, 103 (1996) 854-869 (contains the sequence of the odd-subscripted terms and that of the even-subscripted terms).
Emeric Deutsch, Derangements That Don't Rise Too Fast: 10902, Amer. Math. Monthly, Vol. 110, No. 7 (2003), pp. 639-640.
K. Dilcher and K. B. Stolarsky, Stern polynomials and double-limit continued fractions, Acta Arithmetica 140 (2009), 119-134
R. Kehinde and A. Umar, On the semigroup of partial isometries of a finite chain, arXiv:1101.0049 [math.GR], 2010.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, arXiv:math/0204005 [math.CO], 2002
Index entries for linear recurrences with constant coefficients, signature (1,4,-4).

Cf. A000166, A020988, A020989, A068018.
Cf. A177993. - Gary W. Adamson, May 16 2010
Cf. A183158, A183159. - Abdullahi Umar, Dec 28 2010
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), this sequence (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 31 2011

[(3/8)*2^n +(1/24)*(-2)^n - 2/3: n in [1..35]]; // Vincenzo Librandi, Aug 13 2011

A061547:=n->ceil(abs((3/8)*2^n +(1/24)*(-2)^n - 2/3)); seq(A061547(n), n=1..30); # Wesley Ivan Hurt, Apr 03 2014

f[n_] := (9*2^(n-3) - (-2)^(n-3) - 2)/3; Array[f, 32] (* Robert G. Wilson v, Aug 13 2011 *)

a(n)=(3/8)*2^n+(1/24)*(-2)^n-2/3 \\ Charles R Greathouse IV, Sep 24 2015

a(n) = (3/8)*2^n + (1/24)*(-2)^n - 2/3 for n>=1.
a(n) = 4*a(n-2) + 2, a(0)=1, a(1)=0, a(2)=1.
G.f: (5*z^3-3*z^2-z+1)/((z-1)*(4*z^2-1)).
a(n) = A020989((n-2)/2) for n=2, 4, 6, ... and A020988((n-3)/2) for n=3, 5, 7, ... .
a(n+1)-2*a(n) = A078008 signed. Differences: doubled A000302. - Paul Curtz, Jun 15 2008
a(2i+1) = 2*Sum_{j=0..i-1} 4^j = string "2"^i read in base 4.
a(2i+2) = 4^i + 2*Sum_{j=0..i-1} 4^j = string "1"*"2"^i read in base 4.
a(n+2) = Sum_{k=0..n} A144464(n,k)^2 = Sum_{k=0..n} A152716(n,k). - Philippe Deléham and Michel Marcus, Feb 26 2014
a(2*n-1) = A176965(2*n), a(2*n) = A176965(2*n-1) for n>0. - Yosu Yurramendi, Dec 23 2016
a(2*n-1) = A020988(k-1), a(2*n)= A020989(n-1) for n>0. - Yosu Yurramendi, Jan 03 2017
a(n+2) = 2*A086893(n), n > 0. - Yosu Yurramendi, Mar 07 2017
E.g.f.: (15 - 8*cosh(x) + 5*cosh(2*x) - 8*sinh(x) + 4*sinh(2*x))/12. - Stefano Spezia, Apr 07 2022

a(0)=1 prepended by Alois P. Heinz, Jan 27 2022

A072197 a(n) = 4*a(n-1) + 1 with a(0) = 3.

Original entry on oeis.org

3, 13, 53, 213, 853, 3413, 13653, 54613, 218453, 873813, 3495253, 13981013, 55924053, 223696213, 894784853, 3579139413, 14316557653, 57266230613, 229064922453, 916259689813, 3665038759253, 14660155037013, 58640620148053, 234562480592213, 938249922368853, 3752999689475413

Offset: 0

N. Rathankar (rathankar(AT)yahoo.com), Jul 03 2002

Let A be the Hessenberg matrix of order n, defined by: A[1, j] = 1, A[i, i] := 2, (i > 1), A[i, i - 1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n - 1) = (-1)^n*charpoly(A, -2). - Milan Janjic, Jan 26 2010
Numbers whose binary representation is 11 together with n times 01. For example, 213 = 11010101 (2). - Omar E. Pol, Nov 22 2012
The Collatz-function starting with a(n) will terminate at 1 after 2*n + 7 steps. This is because 3*a(n) + 1 = 5*2^(2n + 1), and the Collatz-function starting with 5 terminates at 1 after 5 additional steps.  So for example, a(2) = 53; Collatz sequence starting with 53 follows: 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (11 steps). - Bob Selcoe, Apr 03 2015
a(n) is also the sum of the numerator and denominator of the binary fractions 0.1, 0.101, 0.10101, 0.1010101... Thus 0.1 = 1/2 with 1 + 2 = 3, 0.101 = 1/2 + 1/8 = 5/8 with 5 + 8 = 13; 0.10101 = 1/2 + 1/8 + 1/32 = 21/32 with 21 + 32 = 53. - J. M. Bergot, Sep 28 2016
a(n), for n >= 2, is also the smallest odd number congruent to 5 modulo 8 for which the modified reduced Collatz map given in A324036 has n consecutive extra steps compared to the reduced Collatz map given in A075677. - Nicolas Vaillant, Philippe Delarue, Wolfdieter Lang, May 09 2019

			a(1) = 13 because a(0) = 3 and 4 * 3 + 1 = 13.
a(2) = 53 because a(1) = 13 and 4 * 13 + 1 = 53.
a(3) = 213 because a(2) = 53 and 4 * 53 + 1 = 213.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Petro Kosobutskyy and Volodymyr Karkulovskyy, Recurrence and structuring of sequences of transformations 3n+ 1 as arguments for confirmation of the Collatz hypothesis, Comp. Des. Sys., Theor. Practice (2023) Vol. 5, No. 1, pp. 28-33. See p. 29.
Petro Kosobutskyy, Anastasiia Yedyharova, and Taras Slobodzyan, From Newton's binomial and Pascal's triangle to Collatz's problem, Comp. Des. Sys., Theor. Practice (2023) Vol. 5, No. 1, pp. 121-127.
Index entries for linear recurrences with constant coefficients, signature (5,-4).
Index entries for sequences related to 3x+1 (or Collatz) problem.

Cf. A000302, A002066 (first differences), A002450, A007583, A020988, A075677, A178415, A324036, A347834.

[(10*4^n-1)/3: n in [0..30]]; // Vincenzo Librandi, Oct 31 2011

A072197:=n->(10*4^n - 1)/3: seq(A072197(n), n=0..30); # Wesley Ivan Hurt, Sep 29 2016

Table[(10(4^n) - 1)/3, {n, 0, 19}] (* Alonso del Arte, Nov 22 2012 *)
NestList[4#+1&,3,30] (* Harvey P. Dale, Mar 09 2019 *)

a(n)=10*4^n\3 \\ Charles R Greathouse IV, Apr 06 2016

Vec((3-2*x)/((1-x)*(1-4*x)) + O(x^30)) \\ Colin Barker, Sep 28 2016

a(n) = (10*4^n - 1)/3 = 10*A002450(n) + 3. - Henry Bottomley, Dec 02 2002
a(n) = 5*a(n-1) - 4*a(n-2), n > 1. - Vincenzo Librandi, Oct 31 2011
a(n) = 2^(2*(n + 1)) - (2^(2*n + 1) + 1)/3 = A000302(n + 1) - A007583(n). - Vladimir Pletser, Apr 12 2014
a(n) = (5*2^(2*n + 1) - 1)/3. - Bob Selcoe, Apr 03 2015
G.f.: (3-2*x)/((1-x)*(1-4*x)). - Colin Barker, Sep 28 2016
a(n) = A020988(n) + A020988(n+1) + 1 = 2*(A002450(n) + A002450(n+1)) + 1. - Yosu Yurramendi, Jan 24 2017
a(n) = A002450(n+1) + 2^(2*n+1). - Adam Michael Bere, May 13 2021
a(n) = a(n-1) + 5*2^(2*n-1), for n >= 1, with a(0) = 3. - Wolfdieter Lang, Aug 16 2021
a(n) = A178415(2,n+1) = A347834(2,n), arrays, for n >= 0. - Wolfdieter Lang, Nov 29 2021
E.g.f.: exp(x)*(10*exp(3*x) - 1)/3. - Elmo R. Oliveira, Apr 02 2025

More terms from Henry Bottomley, Dec 02 2002

A299537 Number of ways to write n^2 as x^2 + y^2 + z^2 + w^2 with x,y,z,w nonnegative integers and z <= w such that x or y is a power of 4 (including 4^0 = 1) and x + 3*y is also a power of 4.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 1, 4, 3, 1, 1, 2, 6, 1, 1, 2, 3, 1, 1, 8, 6, 2, 4, 3, 8, 3, 1, 6, 8, 4, 1, 6, 10, 3, 4, 2, 5, 6, 3, 4, 8, 1, 1, 7, 5, 1, 1, 5, 6, 4, 2, 4, 13, 5, 6, 7, 5, 5, 1, 3, 7, 2, 1, 3, 12, 6, 2, 11, 5, 5, 3, 7, 11, 2, 1, 6, 13, 5, 1

Offset: 1

Zhi-Wei Sun, Mar 04 2018

nonn

Conjecture (i): a(n) > 0 for all n > 0, and a(n) = 1 only for n = 4^k*m with k = 0,1,2,... and m = 1, 2, 3, 5, 7, 11, 15, 19, 43, 47, 135, 1103.
Conjecture (ii): For any integer n > 1, we can write n^2 as x^2 + y^2 + z^2 + w^2 with x,y,z,w nonnegative integers such that 2*x or 2*y is a power of 4 and 2*(x+3*y) is also a power of 4.
Note that 81503^2 cannot be written as x^2 + y^2 + z^2 + w^2 with x,y,z,w nonnegative integers and both x and x + 3*y in the set {4^k: k = 0,1,2,...}. However, 81503^2 = 16372^2 + 4^2 + 52372^2 + 60265^2 with 4 = 4^1 and 16372 + 3*4 = 4^7.
We have verified that the conjecture for n up to 10^7.
See also the related comments in A300219 and A300360, and a similar conjecture in A299794.

			a(2) = 1 since 2^2 = 1^2 + 1^2 + 1^2 + 1^2 with 1 = 4^0 and 1 + 3*1 = 4^1.
a(5) = 1 since 5^2 = 4^2 + 0^2 + 0^2 + 3^2 with 4 = 4^1 and 4 + 3*0 = 4^1.
a(19) = 1 since 19^2 = 1^2 + 0^2 + 6^2 + 18^2 with 1 = 4^0 and 1 + 3*0 = 4^0.
a(43) = 1 since 43^2 = 4^2 + 20^2 + 8^2 + 37^2 with 4 = 4^1 and 4 + 3*20 = 4^3.
a(135) = 1 since 135^2 = 16^2 + 16^2 + 17^2 + 132^2 with 16 = 4^2 and 16 + 3*16 = 4^3.
a(1103) = 1 since 1103^2 = 4^2 + 4^2 + 716^2 + 839^2 with 4 = 4^1 and 4 + 3*4 = 4^2.

Zhi-Wei Sun, Table of n, a(n) for n = 1..2000
Zhi-Wei Sun, Refining Lagrange's four-square theorem, J. Number Theory 175(2017), 167-190.
Zhi-Wei Sun, Restricted sums of four squares, arXiv:1701.05868 [math.NT], 2017-2018.

Cf. A000118, A000290, A000302, A271518, A279612, A281976, A299794, A299924, A300219, A300360, A300362.

SQ[n_]:=SQ[n]=IntegerQ[Sqrt[n]];
Pow[n_]:=Pow[n]=IntegerQ[Log[4,n]];
tab={};Do[r=0;Do[If[(Pow[y]||Pow[4^k-3y])&&SQ[n^2-y^2-(4^k-3y)^2-z^2],r=r+1],{k,0,Log[4,Sqrt[10]*n]},{y,0,Min[n,4^k/3]},{z,0,Sqrt[Max[0,(n^2-y^2-(4^k-3y)^2)/2]]}];tab=Append[tab,r],{n,1,80}];Print[tab]

A345910 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum -1.

Original entry on oeis.org

6, 20, 25, 27, 30, 72, 81, 83, 86, 92, 98, 101, 103, 106, 109, 111, 116, 121, 123, 126, 272, 289, 291, 294, 300, 312, 322, 325, 327, 330, 333, 335, 340, 345, 347, 350, 360, 369, 371, 374, 380, 388, 393, 395, 398, 402, 405, 407, 410, 413, 415, 420, 425, 427

Offset: 1

Gus Wiseman, Jul 01 2021

nonn

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence of terms together with the corresponding compositions begins:
      6: (1,2)
     20: (2,3)
     25: (1,3,1)
     27: (1,2,1,1)
     30: (1,1,1,2)
     72: (3,4)
     81: (2,4,1)
     83: (2,3,1,1)
     86: (2,2,1,2)
     92: (2,1,1,3)
     98: (1,4,2)
    101: (1,3,2,1)
    103: (1,3,1,1,1)
    106: (1,2,2,2)
    109: (1,2,1,2,1)

These compositions are counted by A001791.
A version using runs of binary digits is A031444.
These are the positions of -1's in A124754.
The opposite (positive 1) version is A345909.
The reverse version is A345912.
The version for alternating sum of prime indices is A345959.
Standard compositions: A000120, A066099, A070939, A124754, A228351, A344618.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A000070 counts partitions of 2n+1 with alternating sum 1, ranked by A001105.
A011782 counts compositions.
A097805 counts compositions by sum and alternating sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A345197 counts compositions by sum, length, and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000097, A000346, A008549, A025047, A027187, A031443, A031448, A114121, A119899, A126869, A238279, A344617.

stc[n_]:=Differences[Prepend[Join@@Position[ Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Select[Range[0,100],ats[stc[#]]==-1&]

A345912 Numbers k such that the k-th composition in standard order (row k of A066099) has reverse-alternating sum -1.

Original entry on oeis.org

5, 18, 23, 25, 29, 68, 75, 78, 81, 85, 90, 95, 98, 103, 105, 109, 114, 119, 121, 125, 264, 275, 278, 284, 289, 293, 298, 303, 308, 315, 318, 322, 327, 329, 333, 338, 343, 345, 349, 356, 363, 366, 369, 373, 378, 383, 388, 395, 398, 401, 405, 410, 415, 418, 423

Offset: 1

Gus Wiseman, Jul 01 2021

nonn

The reverse-alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(k-i) y_i.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence of terms together with the corresponding compositions begins:
      5: (2,1)
     18: (3,2)
     23: (2,1,1,1)
     25: (1,3,1)
     29: (1,1,2,1)
     68: (4,3)
     75: (3,2,1,1)
     78: (3,1,1,2)
     81: (2,4,1)
     85: (2,2,2,1)
     90: (2,1,2,2)
     95: (2,1,1,1,1,1)
     98: (1,4,2)
    103: (1,3,1,1,1)
    105: (1,2,3,1)

These compositions are counted by A001791.
These are the positions of -1's in A344618.
The non-reverse version is A345910.
The opposite (positive 1) version is A345911.
The version for Heinz numbers of partitions is A345959.
Standard compositions: A000120, A066099, A070939, A228351, A124754, A344618.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A011782 counts compositions.
A097805 counts compositions by alternating or reverse-alternating sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A344610 counts partitions by sum and positive reverse-alternating sum.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
A345197 counts compositions by sum, length, and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000070, A000346, A001105, A008549, A025047, A031444, A034871, A114121, A126869, A344608, A345958, A345959.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
sats[y_]:=Sum[(-1)^(i-Length[y])*y[[i]],{i,Length[y]}];
Select[Range[0,100],sats[stc[#]]==-1&]

A345917 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum > 0.

Original entry on oeis.org

1, 2, 4, 5, 7, 8, 9, 11, 14, 16, 17, 18, 19, 21, 22, 23, 26, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 42, 44, 45, 47, 52, 56, 57, 59, 62, 64, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82, 84, 85, 87, 88, 89, 90, 91, 93, 94, 95, 100, 104, 105, 107

Offset: 1

Gus Wiseman, Jul 08 2021

nonn

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The initial terms and the corresponding compositions:
     1: (1)
     2: (2)
     4: (3)
     5: (2,1)
     7: (1,1,1)
     8: (4)
     9: (3,1)
    11: (2,1,1)
    14: (1,1,2)
    16: (5)
    17: (4,1)
    18: (3,2)
    19: (3,1,1)
    21: (2,2,1)
    22: (2,1,2)

The version for Heinz numbers of partitions is A026424.
These compositions are counted by A027306.
These are the positions of terms > 0 in A124754.
The weak (k >= 0) version is A345913.
The reverse-alternating version is A345918.
The opposite (k < 0) version is A345919.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A011782 counts compositions.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A345197 counts compositions by sum, length, and alternating sum.
Standard compositions: A000120, A066099, A070939, A228351, A124754, A344618.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000070, A000346, A008549, A025047, A027187, A027193, A032443, A114121, A163493, A344609, A345908.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Select[Range[0,100],ats[stc[#]]>0&]

A299794 Number of ways to write n^2 as x^2 + y^2 + z^2 + w^2 with x >= y >= 0 <= z <= w such that x or 2y is a power of 4 (including 4^0 = 1) and x + 15y is also a power of 4.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 4, 2, 1, 1, 2, 3, 1, 1, 2, 2, 1, 1, 6, 3, 1, 3, 3, 2, 2, 1, 3, 4, 2, 1, 5, 4, 4, 5, 1, 2, 3, 2, 5, 5, 2, 2, 8, 2, 2, 1, 5, 2, 4, 3, 4, 4, 4, 3, 6, 3, 2, 3, 3, 4, 3, 1, 3, 6, 4, 3, 11, 2, 2, 2, 4, 5, 1, 2, 3, 5, 3, 1

Offset: 1

Zhi-Wei Sun, Mar 04 2018

nonn

Conjecture 1: a(n) > 0 for all n > 0. Also, for any integer n > 1 we can write n^2 as x^2 + y^2 + z^2 + w^2 with x >= y >= 0 <= z <= w such that 2*x or y is a power of 4 and also x + 15*y = 2^(2k+1) for some k = 0,1,2,....
Conjecture 2: Let d be 2 or 8, and let r be 0 or 1. Then any positive square n^2 can be written as x^2 + y^2 + z^2 + w^2 with x,y,z,w nonnegative integers such that x or y is a power of 2 and x + d*y = 2^(2k+r) for some k = 0,1,2,....
We have verified Conjecture 1 for n up to 10^7.
See also A299537, A300219 and A300396 for similar conjectures.

			a(2) = 1 since 2^2 = 1^2 + 1^2 + 1^2 + 1^2 with 1 = 4^0 and 1 + 15*1 = 4^2.
a(5) = 1 since 5^2 = 4^2 + 0^2 + 0^2 + 3^2 with 4 = 4^1 and 4 + 15*0 = 4^1.
a(19) = 1 since 19^2 = 1^2 + 0^2 + 6^2 + 18^2 with 1 = 4^0 and 1 + 15*0 = 4^0.
a(159) = 1 since 159^2 = 34^2 + 2^2 + 75^2 + 136^2 with 2*2 = 4^1 and 34 + 15*2 = 4^3.
a(1998) = 1 since 1998^2 = 256^2 + 256^2 + 286^2 + 1944^2 with 256 = 4^4 and 256 + 15*256 = 4^6.
a(3742) = 1 since 3742^2 = 2176^2 + 128^2 + 98^2 + 3040^2 with 2*128 = 4^4 and 2176 + 15*128 = 4^6.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, Refining Lagrange's four-square theorem, J. Number Theory 175(2017), 167-190.
Zhi-Wei Sun, Restricted sums of four squares, arXiv:1701.05868 [math.NT], 2017-2018.

Cf. A000118, A000290, A000302, A271518, A281976, A299537, A299924, A300219, A300356, A300360, A300362, A300396.

SQ[n_]:=SQ[n]=IntegerQ[Sqrt[n]];
Pow[n_]:=Pow[n]=IntegerQ[Log[4,n]];
tab={};Do[r=0;Do[If[Pow[2y]||Pow[4^k-15y],Do[If[SQ[n^2-y^2-(4^k-15y)^2-z^2],r=r+1],{z,0,Sqrt[Max[0,(n^2-y^2-(4^k-15y)^2)/2]]}]],
{k,0,Log[4,Sqrt[226]*n]},{y,0,Min[n,4^(k-2)]}];tab=Append[tab,r],{n,1,80}];Print[tab]

cp's OEIS Frontend

A299924 Number of ways to write n^2 as x^2 + y^2 + z^2 + w^2 with x,y,z,w nonnegative integers such that x + 2*y + 3*z is a power of 4 (including 4^0 = 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A001024 Powers of 15.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

Formula

Extensions

A163493 Number of binary strings of length n which have the same number of 00 and 01 substrings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A061547 Number of 132 and 213-avoiding derangements of {1,2,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A072197 a(n) = 4*a(n-1) + 1 with a(0) = 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A299537 Number of ways to write n^2 as x^2 + y^2 + z^2 + w^2 with x,y,z,w nonnegative integers and z <= w such that x or y is a power of 4 (including 4^0 = 1) and x + 3*y is also a power of 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

A299924 Number of ways to write n^2 as x^2 + y^2 + z^2 + w^2 with x,y,z,w nonnegative integers such that x + 2y + 3z is a power of 4 (including 4^0 = 1).

A299794 Number of ways to write n^2 as x^2 + y^2 + z^2 + w^2 with x >= y >= 0 <= z <= w such that x or 2y is a power of 4 (including 4^0 = 1) and x + 15y is also a power of 4.