A151922 -id:A151922 - cp's OEIS frontend

A130665 a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().

1, 4, 7, 16, 19, 28, 37, 64, 67, 76, 85, 112, 121, 148, 175, 256, 259, 268, 277, 304, 313, 340, 367, 448, 457, 484, 511, 592, 619, 700, 781, 1024, 1027, 1036, 1045, 1072, 1081, 1108, 1135, 1216, 1225, 1252, 1279, 1360, 1387, 1468, 1549, 1792, 1801, 1828, 1855

Offset: 0

N. J. A. Sloane, based on a message from Don Knuth, Jun 23 2007

Partial sums of A048883. - David Applegate, Jun 11 2009
From Gary W. Adamson, Aug 26 2016: (Start)
The formula of Mar 26 2010 is equivalent to the left-shifted vector of matrix powers (lim_{k->infinity} M^k), of the production matrix M:
  1, 0, 0, 0, 0, 0, ...
  4, 0, 0, 0, 0, 0, ...
  3, 1, 0, 0, 0, 0, ...
  0, 4, 0, 0, 0, 0, ...
  0, 3, 1, 0, 0, 0, ...
  0, 0, 4, 0, 0, 0, ...
  0, 0, 3, 1, 0, 0, ...
  ...
The sequence divided by its aerated variant is (1, 4, 3, 0, 0, 0, ...). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
David Applegate, The movie version
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, pp. 27, 31-32.
Tanya Khovanova and Joshua Xiong, Nim Fractals, arXiv:1405.594291 [math.CO], 2014 and J. Int. Seq. 17 (2014) # 14.7.8.
D. E. Knuth, Problem 11320 Amer. Math. Monthly, Vol. 114 No. 9 (Nov 2007) p. 835.
Omar E. Pol, Illustration of initial terms: Fig. 1. Neighbors of the vertices, Fig. 2. Overlapping squares, Fig. 3. One-step bishop, (Nov 08 2009)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Mike Warburton, Ulam-Warburton Automaton - Counting Cells with Quadratics, arXiv:1901.10565 [math.CO], 2019.

Cf. A000120, A006046 (Sum 2^wt(n)), A116520, A130667, A147562, A151920, A151922, A160410, A160412, A360189.

a130665 = sum . map (3 ^) . (`take` a000120_list) . (+ 1)
-- Reinhard Zumkeller, Apr 18 2012

u:=3; a[1]:=1; M:=30; for n from 1 to M do a[2*n] := (u+1)*a[n]; a[2*n+1] := u*a[n] + a[n+1]; od; t1:=[seq( a[n], n=1..2*M )]; # Gives sequence with a different offset

f[n_] := Sum[3^Count[ IntegerDigits[k, 2], 1], {k, 0, n}]; Array[f, 51, 0] (* Robert G. Wilson v, Jun 28 2010 *)

def a(n):  # formula version, n=10^10000 takes ~1 second
    if n == 0:
        return 1
    msb = 1 << (n.bit_length() - 1)
    return msb**2 + 3 * a(n-msb) # Stefan Pochmann, Mar 15 2023

def a(n):  # optimized, n=10^50000 takes ~1 second
    n += 1
    total = 0
    power3 = 1
    while n:
        log = n.bit_length() - 1
        total += power3 << (2*log)
        n -= 1 << log
        power3 *= 3
    return total # Stefan Pochmann, Mar 15 2023

With a different offset: a(1) = 1; a(n) = max { 3*a(k)+a(n-k) | 1 <= k <= n/2 }, for n>1.
a(2n+1) = 4*a(n) and a(2n) = 3*a(n-1) + a(n).
a(n) = (A147562(n+1) - 1)*3/4 + 1. - Omar E. Pol, Nov 08 2009
a(n) = A160410(n+1)/4. - Omar E. Pol, Nov 12 2009
Let r(x) = (1 + 4x + 3x^2), then (1 + 4x + 7x^2 + 16x^3 + ...) =
r(x)* r(x^2) * r(x^4) * r(x^8) * ... - Gary W. Adamson, Mar 26 2010
For asymptotics see the discussion in the comments in A006046. - N. J. A. Sloane, Mar 11 2021
a(n) = Sum_{k=0..floor(log_2(n+1))} 3^k * A360189(n,k). - Alois P. Heinz, Mar 06 2023
a(n) = msb^2 + 3*a(n-msb), where msb = A053644(n). - Stefan Pochmann, Mar 15 2023

Simpler definition (and new offset) from David Applegate, Jun 11 2009

Lower limit of sum in definition changed from 1 to 0 by Robert G. Wilson v, Jun 28 2010

A079314 Number of first-quadrant cells (including the two boundaries) born at stage n of the Holladay-Ulam cellular automaton.

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 4, 10, 2, 4, 4, 10, 4, 10, 10, 28, 2, 4, 4, 10, 4, 10, 10, 28, 4, 10, 10, 28, 10, 28, 28, 82, 2, 4, 4, 10, 4, 10, 10, 28, 4, 10, 10, 28, 10, 28, 28, 82, 4, 10, 10, 28, 10, 28, 28, 82, 10, 28, 28, 82, 28, 82, 82, 244, 2, 4, 4, 10, 4, 10, 10, 28, 4, 10, 10, 28, 10, 28, 28, 82, 4

Offset: 0

N. J. A. Sloane, Feb 12 2003

See the main entry for this CA, A147562, for further information.
When I first read the Singmaster MS in 2003 I misunderstood the definition of the CA. In fact once cells are ON they stay ON. The other version, when cells can change state from ON to OFF, is described in A079317. - N. J. A. Sloane, Aug 05 2009
The pattern has 4-fold symmetry; sequence just counts cells in one quadrant.

			From _Omar E. Pol_, Jul 18 2009: (Start)
If written as a triangle:
  1;
  2;
  2,4;
  2,4,4,10;
  2,4,4,10,4,10,10,28;
  2,4,4,10,4,10,10,28,4,10,10,28,10,28,28,82;
  2,4,4,10,4,10,10,28,4,10,10,28,10,28,28,82,4,10,10,28,10,28,28,82,10,28;...
Rows converge to A151712.
(End)

D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.

Paolo Xausa, Table of n, a(n) for n = 0..10000
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Omar E. Pol, Illustration of initial terms (Overlapping squares) [From _Omar E. Pol_, Nov 20 2009]
D. Singmaster, On the cellular automaton of Ulam and Warburton, 2003 [Cached copy, included with permission]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168, 2015

Cf. A147582, A079315, A079316, A079317, A079318, A079319, A151713, A139250.

Cf. A151712, A151922, A160407.

A079314list[nmax_]:=Join[{1},3^(DigitCount[Range[nmax],2,1]-1)+1];A079314list[100] (* Paolo Xausa, Jun 29 2023 *)

For n > 0, a(n) = 3^(A000120(n)-1) + 1.
For n > 0, a(n) = A147582(n)/4 + 1.
Partial sums give A151922. [Omar E. Pol, Nov 20 2009]

Edited by N. J. A. Sloane, Aug 05 2009

A079316 Number of first-quadrant cells (including the two boundaries) that are ON at stage n of the cellular automaton described in A079317.

Original entry on oeis.org

1, 3, 3, 7, 5, 11, 9, 21, 11, 25, 15, 35, 19, 45, 29, 73, 31, 77, 35, 87, 39, 97, 49, 125, 53, 135, 63, 163, 73, 191, 101, 273, 103, 277, 107, 287, 111, 297, 121, 325, 125, 335, 135, 363, 145, 391, 173, 473, 177, 483, 187, 511, 197, 539, 225, 621, 235, 649, 263, 731

Offset: 0

N. J. A. Sloane, Feb 12 2003

Start with cell (0,0) active; at each succeeding stage the cells that share exactly one edge with an active cell change their state.
The pattern has 4-fold symmetry; sequence just counts cells in one quadrant.
This is not the CA discussed by Singmaster in the reference given in A079314. That was an error based on my misreading of the paper. - N. J. A. Sloane, Aug 05 2009

D. Singmaster, On the cellular automaton of Ulam and Warburton, M500 Magazine of the Open University, #195 (December 2003), pp. 2-7.

David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
D. Singmaster, On the cellular automaton of Ulam and Warburton, 2003 [Cached copy, included with permission]
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS

Cf. A079317, A151922, A151923.

M=matrix(101,101); M[1,1]=1; for(s=1,100, c=[]; a=M[1,1]; for(x=2,100, for(y=2,100, a+=M[x,y]; if(M[x-1,y]+M[x+1,y]+M[x,y-1]+M[x,y+1]==1, c=concat(c,[[x,y]]) )); a+=M[x,1]+M[1,x]; if(M[x,2]==0 && M[x-1,1]+M[x+1,1]==1, c=concat(c,[[x,1]]) ); if(M[2,x]==0 && M[1,x-1]+M[1,x+1]==1, c=concat(c,[[1,x]]) )); print1(a,", "); for(i=1,length(c),M[c[i][1],c[i][2]]=1-M[c[i][1],c[i][2]]) ) \\ Max Alekseyev, Feb 02 2007

More terms from Max Alekseyev, Feb 02 2007

Edited by N. J. A. Sloane, Aug 05 2009

A317626 Intersections with the x-axis of a bouncing ball on a Sophie Germain billiard table.

Original entry on oeis.org

2, 4, 8, 10, 14, 18, 28, 30, 38, 44, 58, 60, 64, 78, 80, 84, 94, 98, 120, 140, 144, 148, 164, 170, 198, 214, 218, 220, 228, 240, 248, 254, 270, 304, 318, 338, 340, 344, 350, 368, 408, 410, 430, 470, 480, 484, 494, 500, 504, 520, 528, 534, 578, 604, 630, 634, 644, 658

Offset: 1

Hilko Koning, Aug 02 2018

nonn

In the first quadrant of a coordinate system define a rectangular Sophie Germain billiard table with width p and length 2p+1, with vertices (0,0), (p,0), (p,2p+1) and (0,2p+1). A billiard ball (considered to be a point) starts from (0,0) at an angle of 45 degrees and hits the sides exactly p times until it hits the x-axis. The sequence gives the intersections with the x-axis of consecutive Sophie Germain prime numbers (p > 3) after p bounces.
The sum of all crossed lattice points (including the rectangle sides) is the sum of crossed points left under, right middle and left up respectively ((p+7)/6)^2 + (p+1)(p+4)/18 + (p+1)(p+7)/36 = ((p+4)/3)^2 (see bouncing examples).
The enclosed areas in the Sophie Germain billiard table also correspond to ((p+4)/3)^2.
The number of trajectories is a subsequence of A176045.
The number of trajectories with slope +1 or with slope -1 is a subsequence of A124485.
The sum of a term of this sequence and the corresponding Sophie Germain prime is A317510 and it appears that this is a subsequence of A179882. Checked up to and including 33295 of A317510 (Sophie Germain prime 24971).

Samuel King, Billiard Simulator
Hilko Koning, Some bouncing examples.

Cf. A005384, A151922, A176045, A124485, A179882, A317510.

a:=[];; for p in [3..2000] do if IsPrime(p) and IsPrime(2*p+1) then Add(a,(p+1)/3); fi; od; a; # Muniru A Asiru, Aug 28 2018

lst = {}; Do[If[PrimeQ[p] && PrimeQ[2 p + 1], AppendTo[lst, (p + 1)/3]], {p, 5, 2*10^3}]; lst
(Select[Prime@ Range[3, 300], PrimeQ[2# + 1] &] + 1)/3 (* Robert G. Wilson v, Aug 02 2018 *)

lista(nn) = forprime(p=2, nn, if (isprime(2*p+1), print1((p+1)/3, ", "));); \\ Michel Marcus, Aug 25 2018

a(n) = (A005384(n)+1)/3 for n>=3. - Michel Marcus, Aug 25 2018

cp's OEIS Frontend

A130665 a(n) = Sum_{k=0..n} 3^wt(k), where wt() = A000120().

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Python

Formula

Extensions

A079314 Number of first-quadrant cells (including the two boundaries) born at stage n of the Holladay-Ulam cellular automaton.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A079316 Number of first-quadrant cells (including the two boundaries) that are ON at stage n of the cellular automaton described in A079317.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A317626 Intersections with the x-axis of a bouncing ball on a Sophie Germain billiard table.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Formula