A049964 -id:A049964 - cp's OEIS frontend

A006257 Josephus problem: a(2n) = 2a(n)-1, a(2n+1) = 2a(n)+1.

0, 1, 1, 3, 1, 3, 5, 7, 1, 3, 5, 7, 9, 11, 13, 15, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

Offset: 0

N. J. A. Sloane

Write the numbers 1 through n in a circle, start at 1 and cross off every other number until only one number is left.
A version of the children's game "One potato, two potato, ...".
a(n)/A062383(n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumerates all binary fractions in the unit interval [0, 1). - Fredrik Johansson, Aug 14 2006
Iterating a(n), a(a(n)), ... eventually leads to 2^A000120(n) - 1. - Franklin T. Adams-Watters, Apr 09 2010
By inspection, the solution to the Josephus Problem is a sequence of odd numbers (from 1) starting at each power of 2.  This yields a direct closed form expression (see formula below). - Gregory Pat Scandalis, Oct 15 2013
Also zero together with a triangle read by rows in which row n lists the first 2^(n-1) odd numbers (see A005408), n >= 1. Row lengths give A011782. Right border gives A000225. Row sums give A000302, n >= 1. See example. - Omar E. Pol, Oct 16 2013
For n > 0: a(n) = n + 1 - A080079(n). - Reinhard Zumkeller, Apr 14 2014
In binary, a(n) = ROL(n), where ROL = rotate left = remove the leftmost digit and append it to the right. For example, n = 41 = 101001_2 => a(n) = (0)10011_2 = 19. This also explains FTAW's comment above. - M. F. Hasler, Nov 02 2016
In the under-down Australian card deck separation: top card on bottom of a deck of n cards, next card separated on the table, etc., until one card is left. The position a(n), for n >= 1, from top will be the left over card. See, e.g., the Behrends reference, pp. 156-164. For the down-under case see 2*A053645(n), for n >= 3, n not a power of 2. If n >= 2 is a power of 2 the botton card survives. - Wolfdieter Lang, Jul 28 2020

			From _Omar E. Pol_, Jun 09 2009: (Start)
Written as an irregular triangle the sequence begins:
  0;
  1;
  1,3;
  1,3,5,7;
  1,3,5,7,9,11,13,15;
  1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31;
  1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,
   43,45,47,49,51,53,55,57,59,61,63;
...
(End)
From _Omar E. Pol_, Nov 03 2018: (Start)
An illustration of initial terms, where a(n) is the area (or number of cells) in the n-th region of the structure:
   n   a(n)       Diagram
   0    0     _
   1    1    |_|_ _
   2    1      |_| |
   3    3      |_ _|_ _ _ _
   4    1          |_| | | |
   5    3          |_ _| | |
   6    5          |_ _ _| |
   7    7          |_ _ _ _|
(End)

Erhard Behrends, Der mathematische Zauberstab, Rowolth Taschenbuch Verlag, rororo 62902, 4. Auflage, 2019, pp. 156-164. [English version: The Math Behind the Magic, AMS, 2019.]
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 10.
M. S. Petković, "Josephus problem", Famous Puzzles of Great Mathematicians, page 179, Amer. Math. Soc. (AMS), 2009.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Paul Weisenhorn, Josephus und seine Folgen, MNU, 59(2006), pp. 18-19.

Iain Fox, Table of n, a(n) for n = 0..100000 (terms 0..1000 from T. D. Noe, terms 1001..10000 from Indranil Ghosh).
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 34.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Daniel Erman and Brady Haran, The Josephus Problem, Numberphile video (2016)
Chris Groër, The Mathematics of Survival: From Antiquity to the Playground, Amer. Math. Monthly, 110 (No. 9, 2003), 812-825.
Alasdair MacFhraing, Aireamh Muinntir Fhinn Is Dhubhain, Agus Sgeul Josephuis Is An Da Fhichead Iudhaich, [Gaelic with English summary], Proc. Royal Irish Acad., Vol. LII, Sect. A., No. 7, 1948, 87-93.
Yuri Nikolayevsky and Ioannis Tsartsaflis, Cohomology of N-graded Lie algebras of maximal class over Z_2, arXiv:1512.87676 [math.RA], (2016), pages 2, 6.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Josephus Problem
Wikipedia, Josephus problem
Index entries for sequences related to the Josephus Problem

Cf. A005428, A035327, A038572, A049940, A049964, A053644, A053645, A088147, A088442.
Second column, and main diagonal, of triangle A032434.
Cf. A181281 (with s=5), A054995 (with s=3).
Column k=2 of A360099.

Require Import ZArith.
Fixpoint a (n : positive) : Z :=
match n with
| xH => 1
| xI n' => (2*(a n') + 1)%Z
| xO n' => (2*(a n') - 1)%Z
end.
(* Stefan Haan, Aug 27 2023 *)

a006257 n = a006257_list !! n
a006257_list =
   0 : 1 : (map (+ 1) $ zipWith mod (map (+ 1) $ tail a006257_list) [2..])
-- Reinhard Zumkeller, Oct 06 2011

[0] cat [2*(n-2^Floor(Log(2,n)))+1: n in [1..100]]; // Vincenzo Librandi, Jan 14 2016

a(0):=0: for n from 1 to 100 do a(n):=(a(n-1)+1) mod n +1: end do:
seq(a(i),i=0..100); # Paul Weisenhorn, Oct 10 2010; corrected by Robert Israel, Jan 13 2016
A006257 := proc(n)
    convert(n,base,2) ;
    ListTools[Rotate](%,-1) ;
    add( op(i,%)*2^(i-1),i=1..nops(%)) ;
end proc: # R. J. Mathar, May 20 2016
A006257 := n -> 2*n  - Bits:-Iff(n, n):
seq(A006257(n), n=0..78); # Peter Luschny, Sep 24 2019

Table[ FromDigits[ RotateLeft[ IntegerDigits[n, 2]], 2], {n, 0, 80}] (* Robert G. Wilson v, Sep 21 2003 *)
Flatten@Table[Range[1, 2^n - 1, 2], {n, 0, 5}] (* Birkas Gyorgy, Feb 07 2011 *)
m = 5; Range[2^m - 1] + 1 - Flatten@Table[Reverse@Range[2^n], {n, 0, m - 1}] (* Birkas Gyorgy, Feb 07 2011 *)

a(n)=sum(k=1,n,if(bitxor(n,k)Paul D. Hanna

a(n)=if(n, 2*n-2^logint(2*n,2)+1, 0) \\ Charles R Greathouse IV, Oct 29 2016

import math
def A006257(n):
     return 0 if n==0 else 2*(n-2**int(math.log(n,2)))+1 # Indranil Ghosh, Jan 11 2017

def A006257(n): return bool(n&(m:=1<Chai Wah Wu, Jan 22 2023
(C#)
static long cs_A006257(this long n) => n == 0 ? 0 : 1 + (1 + (n - 1).cs_A006257()) % n; // Frank Hollstein, Feb 24 2021

To get a(n), write n in binary, rotate left 1 place.
a(n) = 2*A053645(n) + 1 = 2(n-msb(n))+1. - Marc LeBrun, Jul 11 2001. [Here "msb" = "most significant bit", A053644.]
G.f.: 1 + 2/(1-x) * ((3*x-1)/(2-2*x) - Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = number of positive integers k < n such that n XOR k < n. a(n) = n - A035327(n). - Paul D. Hanna, Jan 21 2006
a(n) = n for n = 2^k - 1. - Zak Seidov, Dec 14 2006
a(n) = n - A035327(n). - K. Spage, Oct 22 2009
a(2^m+k) = 1+2*k; with 0 <= m and 0 <= k < 2^m; n = 2^m+k; m = floor(log_2(n)); k = n-2^m; a(n) = ((a(n-1)+1) mod n) + 1; a(1) = 1. E.g., n=27; m=4; k=11; a(27) = 1 + 2*11 = 23. - Paul Weisenhorn, Oct 10 2010
a(n) = 2*(n - 2^floor(log_2(n))) + 1 (see comment above). - Gregory Pat Scandalis, Oct 15 2013
a(n) = 0 if n = 0 and a(n) = 2*a(floor(n/2)) - (-1)^(n mod 2) if n > 0. - Marek A. Suchenek, Mar 31 2016
G.f. A(x) satisfies: A(x) = 2*A(x^2)*(1 + x) + x/(1 + x). - Ilya Gutkovskiy, Aug 31 2019
For n > 0: a(n) = 2 * A062050(n) - 1. - Frank Hollstein, Oct 25 2021

More terms from Robert G. Wilson v, Sep 21 2003

A049939 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 4, where m = 2*n - 2 - 2^(p+1) and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = a(2) = 1 and a(3) = 2.

Original entry on oeis.org

1, 1, 2, 5, 14, 24, 52, 123, 345, 568, 1140, 2299, 4697, 9839, 21409, 50358, 141235, 232113, 464230, 928479, 1857057, 3714559, 7430849, 14869238, 29778995, 59739745, 120175856, 243137792, 497430263, 1039731033, 2262860113

Offset: 1

Clark Kimberling

nonn

			From _Petros Hadjicostas_, Sep 24 2019: (Start)
a(4) = a(1 + A006257(4-2)) + a(1) + a(2) + a(3) = a(2) + a(1) + a(2) + a(3) = 1 + 1 + 1 + 2 = 5.
a(5) = a(1 + A006257(5-2)) + a(1) + a(2) + a(3) + a(4) = a(4) + a(1) + a(2) + a(3) + a(4) = 5 + 1 + 1 + 2 + 5 = 14.
a(6) = a(1 + A006257(6-2)) + a(1) + a(2) + a(3) + a(4) + a(5) = a(2) +  a(1) + a(2) + a(3) + a(4) + a(5) = 1 + 1 + 1 + 2 + 5 + 14 = 24.
(End)

Cf. A006257, A049890 (similar, but with minus a(m/2)), A049891 (similar, but with minus a(m)), A049938 (similar, but with plus a(m/2)), A049940, A049960, A049964.

a := proc(n) local i; option remember; if n < 4 then return [1, 1, 2][n]; end if; add(a(i), i = 1 .. n - 1) + a(2*n - 3 - Bits:-Iff(n - 2, n - 2)); end proc;
seq(a(n), n = 1 .. 37); # Petros Hadjicostas, Sep 24 2019, courtesy of Peter Luschny

a(n) = a(1 + A006257(n-2)) + Sum_{i = 1..n-1} a(i) for n >= 4 with a(1) = a(2) = 1 and a(3) = 2.

Name edited by Petros Hadjicostas, Sep 24 2019

A049940 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 3, where m = 2*n - 3 - 2^(p+1) and p is the unique integer such that 2^p < n - 1 <= 2^(p+1) with a(1) = a(2) = 1.

Original entry on oeis.org

1, 1, 3, 6, 14, 26, 54, 119, 278, 503, 1008, 2027, 4094, 8412, 17554, 38194, 89848, 162143, 324288, 648587, 1297214, 2594652, 5190034, 10383154, 20779768, 41631830, 83498100, 167969126, 339831072, 695251878, 1453222088, 3162777148, 7438945312, 13424668537, 26849337076, 53698674163

Offset: 1

Clark Kimberling

nonn

			From _Petros Hadjicostas_, Sep 24 2019: (Start)
a(3) = a(1) + a(2) + a(m=1) = 1 + 1 + 1 = 3 because m = A006257(3-2) = 2*3 - 3 - 2^ceiling(log[2](3-1)) = 1.
a(4) = a(1) + a(2) + a(3) + a(m=1) = 1 + 1 + 3 + 1 = 6 because m = A006257(4-2) = 2*4 - 3 - 2^ceiling(log[2](4-1)) = 1.
a(5) = a(1) + a(2) + a(3) + a(4) + a(m=3) = 1 + 1 + 3 + 6 + 3 = 14 because m = A006257(5-2) = 2*5 - 3 - 2^ceiling(log[2](5-1)) = 3.
a(6) = a(1) + a(2) + a(3) + a(4) + a(5) + a(m=1) = 1 + 1 + 3 + 6 + 14 + 1 = 26 because m = A006257(6-2) = 2*6 - 3 - 2^ceiling(log[2](6-1)) = 1.
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..3320

Cf. A006257, A049939, A049960, A049964.

a := proc(n) local vv, i; option remember; if n = 1 then vv := 1; end if; if n = 2 then vv := 1; end if; if 3 <= n then vv := 0; for i to n - 1 do vv := vv + a(i); end do; vv := vv + a(2*n - 3 - 2^ceil(log[2](n - 1))); end if; vv; end proc; # Petros Hadjicostas, Sep 24 2019
# second Maple program:
s:= proc(n) option remember; `if`(n<1, 0, a(n)+s(n-1)) end:
a:= proc(n) option remember; `if`(n<3, 1,
      s(n-1)+a(2*(n-2^ilog2(n-2))-3))
    end:
seq(a(n), n=1..36);  # Alois P. Heinz, Sep 24 2019

s[n_] := s[n] = If[n < 1, 0, a[n] + s[n-1]];
a[n_] := a[n] = If[n < 3, 1, s[n-1] + a[2(n - 2^Floor@Log[2, n-2]) - 3]];
Array[a, 36] (* Jean-François Alcover, Apr 23 2020, after Alois P. Heinz *)

a(n) = a(2*n - 3 - 2^ceiling(log_2(n-1))) + Sum_{i = 1..n-1} a(i) = a(A006257(n-2)) + Sum_{i = 1..n-1} a(i) for n >= 3 with a(1) = a(2) = 1. - Petros Hadjicostas, Sep 24 2019

Name edited by and more terms from Petros Hadjicostas, Sep 24 2019

A049960 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 3, where m = 2*n - 3 - 2^(p+1) and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = 1 and a(2) = 2.

Original entry on oeis.org

1, 2, 4, 8, 19, 35, 73, 161, 376, 680, 1363, 2741, 5536, 11375, 23737, 51647, 121495, 219254, 438511, 877037, 1754128, 3508559, 7018105, 14040383, 28098967, 56295692, 112908400, 227132417, 459528811, 940138484, 1965086401, 4276793213, 10059144016, 18153201632, 36306403267

Offset: 1

Clark Kimberling

nonn

Cf. A006257, A049939, A049940, A049964.

a := proc(n) option remember; if n<3 then return [1,2][n] fi; add(a(i), i=1..n-1) + a(2*(n-2) - Bits:-Iff(n-2, n-2)) end: seq(a(n), n=1..37); # Petros Hadjicostas, Sep 24 2019 by modifying a program by Peter Luschny

a(n) = a(A006257(n-2)) + Sum_{i = 1..n-1} a(i) for n >= 3 with a(1) = 1 and a(2) = 2. - Petros Hadjicostas, Sep 24 2019

Name edited and more terms from Petros Hadjicostas, Sep 24 2019

A049938 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 4, where m = n - 1 - 2^p and p is the unique integer such that 2^p < n - 1 <= 2^(p+1), with a(1) = a(2) = 1 and a(3) = 2.

Original entry on oeis.org

1, 1, 2, 5, 10, 20, 40, 81, 165, 326, 652, 1305, 2613, 5231, 10472, 20964, 41969, 83858, 167716, 335433, 670869, 1341743, 2683496, 5367012, 10734065, 21468214, 42936589, 85873504, 171747661, 343496630, 686995878, 1373996997, 2748004486, 5495988009, 10991976018, 21983952037, 43967904077

Offset: 1

Clark Kimberling

nonn

			From _Petros Hadjicostas_, Oct 01 2019: (Start)
a(4) = a(4 - 1 - 2^ceiling(-1 + log_2(3))) + a(1) + a(2) + a(3) = a(1) + a(1) + a(2) + a(3) = 5.
a(5) = a(5 - 1 - 2^ceiling(-1 + log_2(4))) + a(1) + a(2) + a(3) + a(4) = a(2) + a(1) + a(2) + a(3) + a(4) = 10.
a(6) = a(6 - 1 - 2^ceiling(-1 + log_2(5))) + a(1) + a(2) + a(3) + a(4) + a(5) = a(1) + a(1) + a(2) + a(3) + a(4) + a(5) = 20.
(End)

Cf. A006257, A049890 (similar, but with minus a(m)), A049891 (similar, but with minus a(2*m)), A049939 (similar, but with plus a(2*m)), A049940, A049960, A049964, A049978.

a := proc(n) local i; option remember; if n < 4 then return [1, 1, 2][n]; end if; add(a(i), i = 1 .. n - 1) + a(n - 3/2 - 1/2*Bits:-Iff(n - 2, n - 2)); end proc; # Petros Hadjicostas, Oct 01 2019

lista(nn) = { nn = max(nn, 3); my(va = vector(nn)); va[1] = 1; va[2] = 1; va[3] = 2; my(sa = vecsum(va)); for (n=4, nn, va[n] = sa + va[n - 1 - 2^ceil(-1 + log(n-1)/log(2))]; sa += va[n]; ); va; } \\ Petros Hadjicostas, Apr 27 2020

a(n) = a(n - 1 - 2^ceiling(-1 + log_2(n-1))) + Sum_{i = 1..n-1} a(i) = a((1 + A006257(n-2))/2) + Sum_{i = 1..n-1} a(i) for n >= 4 with a(1) = a(2) = 1 and a(3) = 2. - Petros Hadjicostas, Oct 01 2019

More terms from Petros Hadjicostas, Oct 01 2019

A049963 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 4, where m = 2*n - 2 - 2^(p+1) and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = 1, a(2) = 2 and a(3) = 4.

Original entry on oeis.org

1, 2, 4, 9, 25, 43, 93, 220, 617, 1016, 2039, 4112, 8401, 17598, 38292, 90070, 252612, 415156, 830319, 1660672, 3321521, 6643838, 13290772, 26595030, 53262532, 106850150, 214945816, 434874798, 889700788, 1859656696

Offset: 1

Clark Kimberling

nonn

The number m in the definition of the sequence equals 2*n - 2 - x, where x is the smallest power of 2 >= n-1. It turns out that m = 1 + A006257(n-2), where the sequence b(n) = A006257(n) satisfies b(2*n) = 2*b(n) - 1 and b(2*n + 1) = 2*b(n) + 1, and it is related to the so-called Josephus problem. - Petros Hadjicostas, Sep 25 2019

			From _Petros Hadjicostas_, Sep 25 2019: (Start)
a(4) = a(1 + A006257(4-2)) + a(1) + a(2) + a(3) = a(2) + a(1) + a(2) + a(3) = 9.
a(7) = a(1 + A006257(7-2)) + a(1) + a(2) + a(3) + a(4) + a(5) + a(6) = a(4) + a(1) + a(2) + a(3) + a(4) + a(5) + a(6) = 93.
(End)

Index entries for sequences related to the Josephus Problem

Cf. A006257, A049920, A049939, A049960, A049964, A049979.

Cf. A049914 (similar, but with minus a(m/2)), A049915 (similar, but with minus a(m)), A049962 (similar, but with plus a(m/2)).

a := proc(n) local i; option remember; if n < 4 then return [1, 2, 4][n]; end if; add(a(i), i = 1 .. n - 1) + a(2*n - 3 - Bits:-Iff(n - 2, n - 2)); end proc;
seq(a(n), n = 1..40); # Petros Hadjicostas, Sep 25 2019, courtesy of Peter Luschny

a(n) = a(1 + A006257(n-2)) + Sum_{i = 1..n-1} a(i) for n >= 4 with a(1) = 1, a(2) = 2 and a(3) = 4. - Petros Hadjicostas, Sep 25 2019

Name edited by Petros Hadjicostas, Sep 25 2019

A049920 a(n) = a(1) + a(2) + ... + a(n-1) - a(m) for n >= 4, where m = 2*n - 3 - 2^(p+1) and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = 1, a(2) = 3, and a(3) = 2.

Original entry on oeis.org

1, 3, 2, 5, 9, 19, 37, 67, 106, 248, 495, 983, 1938, 3807, 7225, 13007, 20727, 48678, 97355, 194703, 389378, 778687, 1556985, 3112527, 6219767, 12426032, 24775436, 49258849, 97350091, 190037400, 361519131, 650463607, 1036758174

Offset: 1

Clark Kimberling

nonn

The number m in the definition of the sequence equals 2*n - 3 - x, where x is the smallest power of 2 >= n-1. It turns out that m = A006257(n-2), where the sequence b(n) = A006257(n) satisfies b(2*n) = 2*b(n) - 1 and b(2*n + 1) = 2*b(n) + 1, and it is related to the so-called Josephus problem. - Petros Hadjicostas, Sep 25 2019

			From _Petros Hadjicostas_, Sep 25 2019: (Start)
a(4) = -a(A006257(4-2)) + a(1) + a(2) + a(3) = -a(1) + a(1) + a(2) + a(3) = 5.
a(5) = -a(A006257(5-2)) + a(1) + a(2) + a(3) + a(4) = -a(3) + a(1) + a(2) + a(3) + a(4) = 9.
a(6) = -a(A006257(6-2)) + a(1) + a(2) + a(3) + a(4) + a(5) = 19.
a(7) = -a(A006257(7-2)) + a(1) + a(2) + a(3) + a(4) + a(5) + a(6) = 37.
(End)

Robert Israel, Table of n, a(n) for n = 1..3323
Index entries for sequences related to the Josephus Problem

Cf. A006257, A049939, A049960, A049964, A049979.

A[1]:= 1: A[2]:= 3: A[3]:= 2:
for n from 4 to 100 do
  q:= ceil(log[2](n-1));
  m:= 2*n-3-2^q;
  A[n]:= add(A[i],i=1..n-1)-A[m];
od:
seq(A[i],i=1..100); # Robert Israel, Feb 27 2017

a(n) = -a(A006257(n-2)) + Sum_{i = 1..n-1} a(i) for n >= 4 with a(1) = 1, a(2) = 3, and a(3) = 2.

Name edited by Petros Hadjicostas, Sep 25 2019

A049979 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 4, where m = 2*n - 2 - 2^(p+1) and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = 1, a(2) = 3, and a(3) = 4.

Original entry on oeis.org

1, 3, 4, 11, 30, 52, 112, 265, 743, 1224, 2456, 4953, 10119, 21197, 46123, 108490, 304273, 500059, 1000126, 2000293, 4000799, 8002557, 16008843, 32033930, 64155153, 128701875, 258903984, 523810232, 1071651837, 2239971619

Offset: 1

Clark Kimberling

nonn

			From _Petros Hadjicostas_, Sep 24 2019: (Start)
a(4) = a(1 + A006257(4-2)) + a(1) + a(2) + a(3) = a(2) + a(1) + a(2) + a(3) = 3 + 1 + 3 + 4 = 11.
a(7) = a(1 + A006257(7-2)) + a(1) + ... + a(6) = a(4) + a(1) + ... + a(6) = 11 + 1 + 3 + 4 + 11 + 30 + 52 = 112.
(End)

Cf. A006257, A049939, A049940, A049960, A049964.

a := proc(n) local i; option remember; if n < 4 then return [1, 3, 4][n]; end if; add(a(i), i = 1 .. n - 1) + a(2*n - 3 - Bits:-Iff(n - 2, n - 2)); end proc;
seq(a(n), n = 1 .. 37); # Petros Hadjicostas, Sep 24 2019, courtesy of Peter Luschny

a(n) = a(1 + A006257(n-2)) + Sum_{i = 1..n-1} a(i) for n >= 4 with a(1) = 1, a(2) = 3, and a(3) = 4. - Petros Hadjicostas, Sep 24 2019

Name edited by Petros Hadjicostas, Sep 24 2019

A049978 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 4, where m = n - 1 - 2^p and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = 1, a(2) = 3, and a(3) = 4.

Original entry on oeis.org

1, 3, 4, 9, 20, 38, 78, 157, 319, 630, 1262, 2525, 5055, 10121, 20260, 40560, 81199, 162242, 324486, 648973, 1297951, 2595913, 5191844, 10383728, 20767535, 41535232, 83070775, 166142182, 332285627, 664573784, 1329152634, 2658315407, 5316651114, 10633261669, 21266523340, 42533046681, 85066093367, 170132186745

Offset: 1

Clark Kimberling

nonn

			From _Petros Hadjicostas_, Sep 27 2019: (Start)
a(4) = a(4-1-2^ceiling(-1 + log_2(4-1))) + a(1) + a(2) + a(3) = a(1) + a(1) + a(2) + a(3) = 9.
a(5) = a(5-1-2^ceiling(-1 + log_2(5-1))) + a(1) + a(2) + a(3) + a(4) = a(2) + a(1) + a(2) + a(3) + a(4) = 20.
a(6) = a(6-1-2^ceiling(-1 + log_2(6-1))) + a(1) + a(2) + a(3) + a(4) + a(5) = a(1) + a(1) + a(2) + a(3) + a(4) + a(5) = 38.
(End)

Cf. A006257, A049939, A049940, A049960, A049964.

a := proc(n) local i; option remember; if n < 4 then return [1, 3, 4][n]; end if; add(a(i), i = 1 .. n - 1) + a(n - 3/2 - 1/2*Bits:-Iff(n - 2, n - 2)); end proc;
seq(a(n), n = 1 .. 37); # Petros Hadjicostas, Sep 27 2019 using a modification of a program by Peter Luschny

a(n) = a(n - 1 - 2^ceiling(-1 + log_2(n-1))) + Sum_{i = 1..n-1} a(i) = a((1 + A006257(n-2))/2) + Sum_{i = 1..n-1} a(i) for n >= 4 with a(1) = 1, a(2) = 3, and a(3) = 4. - Petros Hadjicostas, Sep 27 2019

Name edited by and more terms from Petros Hadjicostas, Sep 27 2019

cp's OEIS Frontend

A006257 Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Coq

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A049939 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 4, where m = 2*n - 2 - 2^(p+1) and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = a(2) = 1 and a(3) = 2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

Extensions

A049940 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 3, where m = 2*n - 3 - 2^(p+1) and p is the unique integer such that 2^p < n - 1 <= 2^(p+1) with a(1) = a(2) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A049960 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 3, where m = 2*n - 3 - 2^(p+1) and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = 1 and a(2) = 2.

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

Extensions

A049938 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 4, where m = n - 1 - 2^p and p is the unique integer such that 2^p < n - 1 <= 2^(p+1), with a(1) = a(2) = 1 and a(3) = 2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A049963 a(n) = a(1) + a(2) + ... + a(n-1) + a(m) for n >= 4, where m = 2*n - 2 - 2^(p+1) and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = 1, a(2) = 2 and a(3) = 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A049920 a(n) = a(1) + a(2) + ... + a(n-1) - a(m) for n >= 4, where m = 2*n - 3 - 2^(p+1) and p is the unique integer such that 2^p < n-1 <= 2^(p+1), with a(1) = 1, a(2) = 3, and a(3) = 2.

Views

Author

Keywords

A006257 Josephus problem: a(2n) = 2a(n)-1, a(2n+1) = 2a(n)+1.