login
Partial sums of A006257 (Josephus problem).
7

%I #60 Nov 03 2022 08:43:06

%S 0,1,2,5,6,9,14,21,22,25,30,37,46,57,70,85,86,89,94,101,110,121,134,

%T 149,166,185,206,229,254,281,310,341,342,345,350,357,366,377,390,405,

%U 422,441,462,485,510,537,566,597,630,665,702,741,782,825,870,917,966,1017,1070,1125,1182,1241,1302,1365,1366,1369,1374

%N Partial sums of A006257 (Josephus problem).

%C Also total number of ON states after n generations in one of the four wedges of the one-step rook version (or in one of the four quadrants of the one-step bishop version) of the cellular automaton of A256250.

%C A006257 gives the number of cells turned ON at n-th stage.

%C First differs from A255747 at a(11).

%C First differs from A169779 at a(10).

%C It appears that the odd terms (a bisection) give A256250.

%H David A. Corneth, <a href="/A256249/b256249.txt">Table of n, a(n) for n = 0..9999</a>

%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, pp. 37, 41.

%H Yuri Nikolayevsky and Ioannis Tsartsaflis, <a href="http://arxiv.org/abs/1512.07676">Cohomology of N-graded Lie algebras of maximal class over Z_2</a>, arXiv:1512.87676 [math.RA], (2016), page 6.

%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

%F a(n) = (A256250(n+1) - 1)/4.

%e Written as an irregular triangle T(n,k), k >= 1, in which the row lengths are the terms of A011782 the sequence begins:

%e 0;

%e 1;

%e 2, 5;

%e 6, 9, 14, 21;

%e 22, 25, 30, 37, 46, 57, 70, 85;

%e 86, 89, 94,101,110,121,134,149,166,185,206,229,254,281,310,341;

%e ...

%e Right border, a(2^m-1), gives A002450(m) for m >= 0.

%e a(2^m-2) = A203241(m) for m >= 2.

%e It appears that this triangle at least shares with the triangles from the following sequences; A151920, A255737, A255747, the positive elements of the columns k, if k is a power of 2.

%e From _Omar E. Pol_, Jan 03 2016: (Start)

%e Illustration of initial terms in the fourth quadrant of the square grid:

%e ---------------------------------------------------------------------------

%e n a(n) Compact diagram

%e ---------------------------------------------------------------------------

%e 0 0 _

%e 1 1 |_|_ _

%e 2 2 |_| |

%e 3 5 |_ _|_ _ _ _

%e 4 6 |_| | | |

%e 5 9 |_ _| | |

%e 6 14 |_ _ _| |

%e 7 21 |_ _ _ _|_ _ _ _ _ _ _ _

%e 8 22 |_| | | | | | | |

%e 9 25 |_ _| | | | | | |

%e 10 30 |_ _ _| | | | | |

%e 11 37 |_ _ _ _| | | | |

%e 12 46 |_ _ _ _ _| | | |

%e 13 57 |_ _ _ _ _ _| | |

%e 14 70 |_ _ _ _ _ _ _| |

%e 15 85 |_ _ _ _ _ _ _ _|

%e .

%e a(n) is also the total number of cells in the first n regions of the diagram. A006257(n) gives the number of cells in the n-th region of the diagram.

%e (End)

%t (* Based on _Birkas Gyorgy_'s code in A006257 *)

%t Accumulate[Prepend[Flatten[Table[Range[1,2^n-1,2],{n,0,7}]],0]] (* _Ivan N. Ianakiev_, Mar 30 2015 *)

%o (PARI) a(n)=n++;b=#binary(n>>1);(4^b-1)/3+(n-2^b)^2 \\ _David A. Corneth_, Mar 21 2015

%Y Cf. A002450, A006257, A011782, A139250, A151920, A169779, A255737, A255747, A256250, A256251, A266540.

%K nonn,look

%O 0,3

%A _Omar E. Pol_, Mar 20 2015