A006257 -id:A006257 - cp's OEIS frontend

A378635 Triangle T(n,k) read by rows, where row n is a permutation of numbers 1 through n, such that if the deck of n cards is prepared in this order, and under-down dealing is used, then the resulting cards are put down in increasing order.

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

Offset: 1

Tanya Khovanova and the MIT PRIMES STEP junior group, Dec 02 2024

Under-down dealing is a dealing pattern where the top card is put on the bottom of the deck, and the next card is dealt. Then, this pattern repeats until all cards are dealt.
This card dealing is related to the Josephus problem. The card in row n and column k is x if and only if in the Josephus problem with n people, the person number x is the k-th person eliminated. Equivalently, each row of Josephus triangle A321298 is an inverse permutation of the corresponding row of this triangle.
The total number of moves for row n is 2n.
The first column is A225381, the order of elimination of the first person in the Josephus problem.
The index of the largest number in row n is A006257(n), corresponding to the index of the freed person in the Josephus problem.
T(n,2j) = j, for 2j <= n.

			Suppose there are four cards arranged in order 4,1,3,2. Card 4 goes under, and card 1 is dealt. Now the deck is ordered 3,2,4. Card 3 goes under, and card 2 is dealt. Now the leftover deck is ordered 4,3. Card 4 goes under, and card 3 is dealt. Then card 4 goes under, and card 4 is dealt. The dealt cards are in order. Thus, the fourth row of the triangle is 4,1,3,2.
Triangle begins:
  1;
  2, 1;
  2, 1, 3;
  4, 1, 3, 2;
  3, 1, 5, 2, 4;
  5, 1, 4, 2, 6, 3;
  4, 1, 6, 2, 5, 3, 7;
  8, 1, 5, 2, 7, 3, 6, 4;
  5, 1, 9, 2, 6, 3, 8, 4, 7;

Cf. A005843, A006257, A225381, A321298.

T(1,1) = 1, for n > 1, T(n,1) = T(n-1,n-1) + 1 and T(n,2) = 1. For n > 1 and k > 2, T(n,k) = T(n-1,k-2) + 1.

A038572 a(n) = n rotated one binary place to the right.

Original entry on oeis.org

0, 1, 1, 3, 2, 6, 3, 7, 4, 12, 5, 13, 6, 14, 7, 15, 8, 24, 9, 25, 10, 26, 11, 27, 12, 28, 13, 29, 14, 30, 15, 31, 16, 48, 17, 49, 18, 50, 19, 51, 20, 52, 21, 53, 22, 54, 23, 55, 24, 56, 25, 57, 26, 58, 27, 59, 28, 60, 29, 61, 30, 62, 31, 63, 32, 96, 33, 97, 34, 98, 35, 99, 36, 100

Offset: 0

Marc LeBrun

Iterating a(n), a(a(n)), ... eventually leads to 2^A000120(n) - 1. - Franklin T. Adams-Watters, Apr 09 2010

			For n = 35, 35_10 = 100011_2, which after rotating one binary place to the right becomes 110001. Now, 110001_2 = 49_10. So, a(35) = 49. - _Indranil Ghosh_, Jan 21 2017

Indranil Ghosh, Table of n, a(n) for n = 0..20000 (first 1024 terms from T. D. Noe)

Cf. A006257, A088146.

a038572 0 = 0
a038572 n = a053645 n * m + n' where (n', m) = divMod n 2
-- Reinhard Zumkeller, Dec 03 2012

A038572 := 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

Table[ FromDigits[ RotateRight[ IntegerDigits[n, 2]], 2], {n, 0, 80}] (* Robert G. Wilson v *)

a(n)=if(n<2,return(n)); my(d=binary(n)); fromdigits(concat(d[#d], d[1..#d-1]),2) \\ Charles R Greathouse IV, Sep 02 2015

def A038572(n):
    x = bin(n)[2:]
    return int(x[-1]+x[:-1],2) # Indranil Ghosh, Jan 21 2017

def A038572(n): return (n>>1)+(1<Chai Wah Wu, Jan 22 2023

a(n) = A053645(n) * A000035(n) + A004526(n) = most significant bit(n) * least significant bit(n) + floor(n/2).

a(0)=0, a(1)=1, a(2n) = n, a(2n+1) = 2a(n) + 2a(n+1) - n. - Ralf Stephan, Oct 24 2003

A054995 A version of Josephus problem: a(n) is the surviving integer under the following elimination process. Arrange 1,2,3,...,n in a circle, increasing clockwise. Starting with i=1, delete the integer two places clockwise from i. Repeat, counting two places from the next undeleted integer, until only one integer remains.

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 4, 7, 1, 4, 7, 10, 13, 2, 5, 8, 11, 14, 17, 20, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 1, 4, 7, 10, 13, 16, 19, 22, 25

Offset: 1

John W. Layman, May 30 2000

nonn

If one counts only one place (rather than two) at each stage to determine the element to be deleted, the Josephus survivors (A006257) are obtained.

			a(5) = 4 because the elimination process gives (1^,2,3,4,5) -> (1,2,4^,5) -> (2^,4,5) -> (2^,4) -> (4), where ^ denotes the counting reference position.
a(13) = 13 => a(14) = (a(13) + 2) mod 14 + 1 = 2. - _Paul Weisenhorn_, Oct 10 2010

Arkadiusz Wesolowski, Table of n, a(n) for n = 1..10000
R. Baumann, Das Josephus-Problem, LOG IN, Heft Nr. 165, pp. 70-71, 2010 (in German).
Ph. Dumas, Algebraic aspects of B-regular series. [Broken link]
Philippe Dumas, Algebraic aspects of B-regular series, Research Report, RR-1931, INRIA, 1993.
Ph. Dumas, Algebraic aspects of B-regular series, in: International Colloquium on Automata, Languages and Programming, ICALP 1993 (A. Lingas, R. Karlsson, S. Carlsson, eds.), pp. 457-468, Lecture Notes in Computer Science, vol. 700, Springer, Berlin, 1993.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, J. Théor. Nombres Bordeaux 9 (1997), no. 2, 303-318.
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.
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33, 235-240, 1991.
Index entries for sequences related to the Josephus Problem

Cf. A032434, A005427, A005428, A006257, A007495, A000960, A056530.

Cf. A181281 (with s=5). - Paul Weisenhorn, Oct 10 2010

(* First do *) Needs["Combinatorica`"] (* then *) f[n_] := Last@ InversePermutation@ Josephus[n, 3]; Array[f, 70] (* Robert G. Wilson v, Jul 31 2010 *)
Table[Nest[Rest@RotateLeft[#, 2] &, Range[n], n - 1], {n, 72}] // Flatten (* Arkadiusz Wesolowski, Jan 14 2013 *)

a(n) = 3*n + 1 - floor(K(3)*(3/2)^(ceiling(log((2*n+1)/K(3))/log(3/2)))) where K(3) = (3/2)*K = 1.622270502884767... (K is the constant described in A061419); a(n) = 3n + 1 - A061419(k+1) where A061419(k+1) is the least integer such that A061419(k+1) > 2n.
a(1) = 1 and, for n > 1, a(n) = (a(n-1) + 3) mod n, if this value is nonzero, n otherwise.
a(n) = (a(n-1) + 2) mod n + 1. - Paul Weisenhorn, Oct 10 2010

A080079 Least number causing the longest carry sequence when adding numbers <= n to n in binary representation.

Original entry on oeis.org

1, 2, 1, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47

Offset: 1

Reinhard Zumkeller, Jan 26 2003

T(n,k) < T(n,a(n)) = A070940(n) for 1 <= k < a(n) and T(n,k) <= T(n,a(n)) for a(n) <= k <= n, where T is defined as in A080080.

a(n) gives the distance from n to the nearest 2^t > n. - Ctibor O. Zizka, Apr 09 2020

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n

Cf. A327489, A004755, A062383, A080080, A240769, A006257.

a080079 n = (length $ takeWhile (< a070940 n) (a080080_row n)) + 1
-- Reinhard Zumkeller, Apr 22 2013

[-n+2*2^Floor(Log(n)/Log(2)): n in [1..80]]; // Vincenzo Librandi, Dec 01 2016

# Alois P. Heinz observes in A327489:
A080079 := n -> 1 + Bits:-Nor(n, n):
# Likewise:
A080079 := n -> 1 + Bits:-Nand(n, n):
seq(A080079(n), n=1..81); # Peter Luschny, Sep 23 2019

Flatten@Table[Nest[Most[RotateRight[#]] &, Range[n], n - 1], {n, 30}] (* Birkas Gyorgy, Feb 07 2011 *)
Table[FromDigits[(IntegerDigits[n, 2] /. {0 -> 1, 1 -> 0}), 2] +
1, {n, 30}] (* Birkas Gyorgy, Feb 07 2011 *)
Table[BitXor[n, 2^IntegerPart[Log[2, n] + 1] - 1] + 1, {n, 30}] (* Birkas Gyorgy, Feb 07 2011 *)
Table[2 2^Floor[Log[2, n]] - n, {n, 30}] (* Birkas Gyorgy, Feb 07 2011 *)
Flatten@Table[Reverse@Range[2^n], {n, 0, 4}] (* Birkas Gyorgy, Feb 07 2011 *)

def A080079(n): return (1 << n.bit_length())-n # Chai Wah Wu, Jun 30 2022

From Benoit Cloitre, Feb 22 2003: (Start)
a(n) = A004755(n) - 2*n.
a(n) = -n + 2*2^floor(log(n)/log(2)). (End)
From Ralf Stephan, Jun 02 2003: (Start)
a(n) = n iff n = 2^k, otherwise a(n) = A035327(n-1).
a(n) = A062383(n) - n. (End)
a(0) = 0, a(2*n) = 2*a(n), a(2*n+1) = 2*a(n)-1 + 2*[n==0]. - Ralf Stephan, Jan 04 2004
a(n) = A240769(n,1); A240769(n, a(n)) = 1. - Reinhard Zumkeller, Apr 13 2014
a(n) = n + 1 - A006257(n). - Reinhard Zumkeller, Apr 14 2014

A062050 n-th chunk consists of the numbers 1, ..., 2^n.

Original entry on oeis.org

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

Offset: 1

Marc LeBrun, Jun 30 2001

a(k) is the distance between k and the largest power of 2 not exceeding k, where k = n + 1. [Consider the sequence of even numbers <= k; after sending the first term to the last position delete all odd-indexed terms; the final term that remains after iterating the process is the a(k)-th even number.] - Lekraj Beedassy, May 26 2005

Triangle read by rows in which row n lists the first 2^(n-1) positive integers, n >= 1; see the example. - Omar E. Pol, Sep 10 2013

			From _Omar E. Pol_, Aug 31 2013: (Start)
Written as irregular triangle with row lengths A000079:
  1;
  1, 2;
  1, 2, 3, 4;
  1, 2, 3, 4, 5, 6, 7, 8;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16;
  ...
Row sums give A007582.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions. [ps file]
Ralf Stephan, Table of generating functions. [pdf file]

Cf. A053644, A053645.

Cf. A092754.

a062050 n = if n < 2 then n else 2 * a062050 n' + m - 1
            where (n',m) = divMod n 2
-- Reinhard Zumkeller, May 07 2012

A062050 := proc(n) option remember; if n < 4 then return [1, 1, 2][n] fi;
2*A062050(floor(n/2)) + irem(n,2) - 1 end:
seq(A062050(n), n=1..89); # Peter Luschny, Apr 27 2020

Flatten[Table[Range[2^n],{n,0,6}]] (* Harvey P. Dale, Oct 12 2015 *)

PARI
```
a(n)=floor(n+1-2^logint(n,2))
```

a(n)= n - 1<Ruud H.G. van Tol, Dec 13 2024

def A062050(n): return n-(1<Chai Wah Wu, Jan 22 2023

a(n) = A053645(n) + 1.
a(n) = n - msb(n) + 1 (where msb(n) = A053644(n)).
a(n) = 1 + n - 2^floor(log(n)/log(2)). - Benoit Cloitre, Feb 06 2003; corrected by Joseph Biberstine (jrbibers(AT)indiana.edu), Nov 25 2008
G.f.: 1/(1-x) * ((1-x+x^2)/(1-x) - Sum_{k>=1} 2^(k-1)*x^(2^k)). - Ralf Stephan, Apr 18 2003
a(1) = 1, a(2*n) = 2*a(n) - 1, a(2*n+1) = 2*a(n). - Ralf Stephan, Oct 06 2003
A005836(a(n+1)) = A107681(n). - Reinhard Zumkeller, May 20 2005
a(n) = if n < 2 then n else 2*a(floor(n/2)) - 1 + n mod 2. - Reinhard Zumkeller, May 07 2012
Without the constant 1, Ralf Stephan's g.f. becomes A(x) = x/(1-x)^2 - (1/(1-x)) * Sum_{k>=1} 2^(k-1)*x^(2^k) and satisfies the functional equation A(x) - 2*(1+x)*A(x^2) = x*(1 - x - x^2)/(1 - x^2). - Petros Hadjicostas, Apr 27 2020
For n > 0: a(n) = (A006257(n) + 1) / 2. - Frank Hollstein, Oct 25 2021

A006165 a(1) = a(2) = 1; thereafter a(2n+1) = a(n+1) + a(n), a(2n) = 2a(n).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

a(n+1) is the second-order survivor of the n-person Josephus problem where every second person is marked until only one remains, who is then eliminated; the process is repeated from the beginning until all but one is eliminated. a(n) is first a power of 2 when n is three times a power of 2. For example, the first appearances of 2, 4, 8 and 16 are at positions 3, 6, 12 and 24, or (3*1),(3*2),(3*4) and (3*8). Eugene McDonnell (eemcd(AT)aol.com), Jan 19 2002, reporting on work of Boyko Bantchev (Bulgaria).
Appears to coincide with following sequence: Let n >= 1. Start with a bag B containing n 1's. At each step, replace the two least elements x and y in B with the single element x+y. Repeat until B contains 2 or fewer elements. Let a(n) be the largest element remaining in B at this point. - David W. Wilson, Jul 01 2003
Hsien-Kuei Hwang, S Janson, TH Tsai (2016) show that A078881 is the same sequence, apart from the offset. - N. J. A. Sloane, Nov 26 2017

			From _Peter Bala_, Aug 01 2022: (Start)
1) The sequence {n - a(a(n)) : n >= 1} begins [0, 1, 2, 3, 3, 4, 5, 6, 6, 6, 7, 8, 9, 10, 11, 12, 12, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 49, ...] has the repeated values 3 (twice), 6 (three times), 12 (five times), 24 (nine times), 48 (seventeen times) ..., conjecturally of the form 3*2^m
2) The sequence {n - a(a(a(n))) : n >= 1} begins [0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 14, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 28, 28, 28, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, ...] has the repeated values 7 (twice), 14 (three times), 28 (five times), 56 (nine times) ..., conjecturally of the form 7*2^m. (End)

J. Arkin, D. C. Arney, L. S. Dewald and W. E. Ebel, Jr., Families of recursive sequences, J. Rec. Math., 22 (No. 22, 1990), 85-94.
Hsien-Kuei Hwang, S Janson, TH Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585
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 = 1..1024
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Dale Gerdemann, Second-Order Josephus Problem (video)
Jeffrey Shallit, Intertwining of Complementary Thue-Morse Factors, arXiv:2203.02917 [cs.FL], 2022.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index entries for sequences related to the Josephus Problem

Cf. A053644, A060973, A066997, A078881.

a := proc (n) option remember; if n = 1 then 1 else n - a(n - a(a(n-1))) end if end proc: seq(a(n), n = 1..100); # Peter Bala, Jul 31 2022

t = {1, 1}; Do[If[OddQ[n], AppendTo[t, t[[Floor[n/2]]] + t[[Ceiling[n/2]]]], AppendTo[t, 2*t[[n/2]]]], {n, 3, 128}] (* T. D. Noe, May 25 2011 *)

a(n) = my(i=logint(n,2)-1); if(bittest(n,i), 2<Kevin Ryde, Aug 06 2022

a(n)=if(n<2,1,n-a(n-a(n\2))); \\ Benoit Cloitre, May 12 2024

from functools import lru_cache
@lru_cache(maxsize=None)
def A006165(n): return 1 if n <= 2 else A006165(n//2) + A006165((n+1)//2) # Chai Wah Wu, Mar 08 2022

def A006165(n): return min(n-(m:=1<1 else 1 # Chai Wah Wu, Oct 22 2024

For n >= 2, if a(n) >= A006257(n), i.e., if msb(n) > n - a(n)/2, then a(n+1) = a(n)+1, otherwise a(n+1) = a(n). - Henry Bottomley, Jan 21 2002
a(n+1) = min(msb(n), 1+n-msb(n)/2) for all n (msb = most significant bit, A053644). - Boyko Bantchev (bantchev(AT)math.bas.bg), May 17 2002
a(1)=1, a(n) = n - a(n - a(a(n-1))). - Benoit Cloitre, Nov 08 2002
a(1)=1, a(n) = n - a(n - a(floor(n/2))). - Benoit Cloitre, May 12 2024
For k > 0, 0 <= i <= 2^k-1, a(2^k+i) = 2^(k-1)+i; for 2^k-2^(k-2) <= x <= 2^k a(x) = 2^(k-1); (also a(m*2^k) = a(m)*2^k for m >= 2). - Benoit Cloitre, Dec 16 2002
G.f.: x * (1/(1+x) + (1/(1-x)^2) * Sum_{k>=0} t^2*(1-t)) where t = x^2^k. - Ralf Stephan, Sep 12 2003
a(n) = A005942(n+1)/2 - n = n - A060973(n) = 2n - A007378(n). - Ralf Stephan, Sep 13 2003
a(n) = A080776(n-1) + A060937(n). - Ralf Stephan
From Peter Bala, Jul 31 2022: (Start)
For k a positive integer, define the k-th iterated sequence a^(k) of a by a^(1)(n) = a(n) and setting a^(k)(n) = a^(k-1)(a(n)) for k >= 2. For example, a^(2)(n) = a(a(n)) and a^(3)(n) = a(a(a(n))).
Conjectures: for n >= 2 there holds
(i) a(n) + a(n - a(n - a(n - a(n - a(n))))) = n;
(ii) a(n - a(n - a(n - a(n)))) = a(n - a(n - a(n - a(n - a(n - a(n))))));
(iii) a^2(n) = a(n - a(n - a(n - a(n))));
(iv) n - a(n) = a(n - a^(2)(n));
(v) a(n - a(n)) = a^(2)(n - a^(2)(n - a^(2)(n - a^(2)(n))));
(vi) for k >= 2, a^(k)(n - a^(k)(n)) = a^(k)(n - a^(k)(n - a^(k)(n - a^(k)(n)))).
(vii) for k >= 1, the sequence {n - a^(k)(n) : n >= 1} has first differences either 0 or 1. We conjecture that the repeated values of the sequence are of the form (2^k - 1)*2^m. The number of repeated values appears to always be 2, 3, 5, 9, 17, 35, ..., independent of k, conjecturally A000051. Two examples are given below.
A similar property may hold for the sequences {n - A060973^(k)(n) : n >= 2^(k-1)}, k = 1,2,3,.... (End)

More terms from Larry Reeves (larryr(AT)acm.org), Jun 12 2002

A032434 Triangle read by rows: last survivors of Josephus elimination process.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

T(n,k) is the surviving integer under the following elimination process. Arrange 1, 2, 3, ..., n in a circle, increasing clockwise. Starting with i = 1, delete the integer k - 1 places clockwise from i. Repeat, counting k - 1 places from the next undeleted integer, until only one integer remains. [After John W. Layman]
From Gerhard Kirchner, Jan 08 2017: (Start)
The fast recurrence is useful for large n, if single values of T(n,k) are to be determined (not the whole sequence). The number of steps is about log(n)/log(n/(k/(k-1))) instead of n, i.e., many basic steps are bypassed by a shortcut.
Example: For computing T(10^80, 7), about 1200 steps are needed, done in a second, whereas even the age of the universe would not be sufficient for the basic recurrence. Deduction of the fast recurrence and the reason for its efficiency: See the link "Fast recurrence". (End)

			Triangle T(n,k) (with rows n >= 1 and columns k = 1..n) begins
  1;
  2, 1;
  3, 3, 2;
  4, 1, 1, 2;
  5, 3, 4, 1, 2;
  6, 5, 1, 5, 1, 4;
  7, 7, 4, 2, 6, 3, 5;
  ...
Fast recurrence for n = 7 and k = 3:
m =    1 2 3 4 5 6,
z(m) = 1 2 3 4 6 9,
r(m) = 1 2 2 1 1,
z(6) > n => M = 5.
Result: T(7,3) = r(5) + 3*(n - z(5)) = 4.

W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987, see pp. 32-36.
M. Kraitchik, "Josephus' Problem." Sec. 3.13 in Mathematical Recreations. New York: W. W. Norton, pp. 93-94, 1942.

T. D. Noe, Rows n = 1..50, flattened
Philippe Dumas, Algebraic aspects of B-regular series, inria-00074743, 1993.
Philippe Dumas, Algebraic aspects of B-regular series, in: A. Lingas, R. Karlsson, S. Carlsson S. (eds), Automata, Languages and Programming, ICALP 1993 (Lecture Notes in Computer Science, vol 700, Springer, Berlin, Heidelberg), pp. 457-468, 1993.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, preprint, 1997.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, preprint, 1997.
L. Halbeisen and N. Hungerbühler, The Josephus Problem, Journal de Théorie des Nombres de Bordeaux 9 (1997), 303-318.
Gerhard Kirchner, Fast recurrence.
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, preprint, 1991. [Cached copy, with permission]
A. M. Odlyzko and H. S. Wilf, Functional iteration and the Josephus problem, Glasgow Math. J. 33 (1991), 235-240.
Eric Weisstein's World of Mathematics, Josephus Problem.
Wikipedia, Josephus problem.
Index entries for sequences related to the Josephus problem

Cf. A032435, A032436, A321781.

Second column is A006257, third column is A054995. Diagonal T(n, n) is A007495.

t[1, k_] = 1; t[n_, k_] := t[n, k] = If[m = Mod[t[n-1, k] + k, n]; m != 0, m, n]; Flatten[ Table[ t[n, k], {n, 1, 14}, {k, 1, n}]] (* Jean-François Alcover, Sep 25 2012 *)

T(n,k)=local(t): if(n<2,n>0,t=(T(n-1,k)+k)%n: if(t,t,n))

Recurrence: T(1, k) = 1, T(n, k) = (T(n-1, k) + k) mod n if this is nonzero and n if not.
From Gerhard Kirchner, Jan 08 2017: (Start)
The same recurrence without these conditions:
T(1, k) = 1,  T(n, k) = 1 + (T(n-1, k) + k - 1) mod n.
This "basic" recurrence is used in the following:
Fast recurrence (n >= k):
z(1) = 1, r(1) = 1,
if z(m) < k-1 then
  z(m+1) = z(m) + 1,
  r(m+1) = 1 + (r(m)+k-1) mod z(m+1) (basic recurrence),
else
  e(m) = -z(m) mod (k-1),
  if r(m) + e(m) <= 0 then e(m) -> e(m) + k - 1,
  z(m+1) = z(m) + (z(m) + e(m))/(k-1),
  r(m+1) = r(m) + e(m).
Result for m = M with z(M) <= n < z(M+1):
T(n,k) = r(M) + k(n - z(M)). (End)
From Gerhard Kirchner, Jan 12 2017: (Start)
Another fast (and shorter) recurrence is given in "Functional iteration and the Josephus problem", p. 1, (see link):
D(m,k) = ceiling(k/(k-1)*D(m-1,k)), m >= 1; D(0,k)=1.
Result for m with D(m-1,k) <= (k-1)*n < D(m,k):
T(n,k) = k*n + 1 - D(m,k). (End)

Edited by Ralf Stephan, May 18 2004

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

Original entry on oeis.org

1, 1, 2, 3, 4, 7, 9, 10, 11, 21, 30, 37, 41, 44, 46, 47, 48, 95, 141, 185, 226, 263, 293, 314, 325, 335, 344, 351, 355, 358, 360, 361, 362, 723, 1083, 1441, 1796, 2147, 2491, 2826, 3151, 3465, 3758, 4021, 4247, 4432, 4573, 4668, 4716

Offset: 1

Clark Kimberling

nonn

Ivan Neretin, Table of n, a(n) for n = 1..8193

Cf. A006257, A050025 (similar, but with different initial conditions).

a := proc(n) option remember;
`if`(n < 4, [1, 1, 2][n], a(n - 1) + a(Bits:-Iff((n - 2) $ 2) + 3 - n));
end proc;
seq(a(n), n = 1 .. 50); # Petros Hadjicostas, Nov 07 2019

Fold[Append[#1, #1[[-1]] + #1[[#2]]] &, {1, 1, 2}, Flatten@Table[k, {n, 5}, {k, 2^n, 1, -1}]] (* Ivan Neretin, Sep 06 2015 *)

From Petros Hadjicostas, Nov 08 2019: (Start)
a(n) = a(2^ceiling(log_2(n-1)) + 2 - n) + a(n-1) for n >= 4.
a(n) = a(n - 1 - A006257(n-2)) + a(n-1) for n >= 4. (End)

Name edited by Petros Hadjicostas, Nov 07 2019

A255689 Convert n to base 4, move the most significant digit to the least significant one and convert back to base 10.

Original entry on oeis.org

0, 1, 2, 3, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15, 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59, 63, 1, 5, 9, 13, 17, 21, 25

Offset: 0

Paolo P. Lava, Mar 02 2015

a(4*n) = 1.

Fixed points of the transform are listed in A048329.

			11 in base 4 is 23: moving the most significant digit as the least significant one we have 32 that is 14 in base 10.

Indranil Ghosh, Table of n, a(n) for n = 0..65536 (terms 0..1000 from Paolo P. Lava)

Cf. A006257, A030103, A255588-A255594, A048787, A255690-A255693.

with(numtheory): P:=proc(q,h) local a,b,k,n; print(0);
for n from 1 to q do
a:=convert(n,base,h); b:=[]; for k from 1 to nops(a)-1 do b:=[op(b),a[k]]; od; a:=[a[nops(a)],op(b)];
a:=convert(a,base,h,10); b:=0; for k from nops(a) by -1 to 1 do b:=10*b+a[k]; od;
print(b); od; end: P(10^4,4);

roll[n_, b_] := Block[{w = IntegerDigits[n, b]}, Append[Rest@ w, First@ w]]; b = 4; FromDigits[#, b] & /@ (roll[#, b] & /@ Range[0, 70]) (* Michael De Vlieger, Mar 04 2015 *)
Table[FromDigits[RotateLeft[IntegerDigits[n,4]],4],{n,0,70}] (* Harvey P. Dale, Aug 07 2015 *)

def A255689(n):
    x=A007090(n)
    return int (x[1:]+x[0],4) # Indranil Ghosh, Feb 08 2017

A255693 Convert n to base 8, move the most significant digit to the least significant one and convert back to base 10.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 1, 9, 17, 25, 33, 41, 49, 57, 2, 10, 18, 26, 34, 42, 50, 58, 3, 11, 19, 27, 35, 43, 51, 59, 4, 12, 20, 28, 36, 44, 52, 60, 5, 13, 21, 29, 37, 45, 53, 61, 6, 14, 22, 30, 38, 46, 54, 62, 7, 15, 23, 31, 39, 47, 55, 63, 1, 9, 17, 25, 33, 41

Offset: 0

Paolo P. Lava, Mar 02 2015

a(8*n) = 1.

Fixed points of the transform are listed in A048333.

			13 in base 8 is 15: moving the most significant digit as the least significant one we have 51 that is 41 in base 10.

Paolo P. Lava, Table of n, a(n) for n = 0..1000

Cf. A006257, A030107, A255588-A255594, A255689-A255692.

with(numtheory): P:=proc(q,h) local a,b,k,n; print(0);
for n from 1 to q do
a:=convert(n,base,h); b:=[]; for k from 1 to nops(a)-1 do b:=[op(b),a[k]]; od; a:=[a[nops(a)],op(b)];
a:=convert(a,base,h,10); b:=0; for k from nops(a) by -1 to 1 do b:=10*b+a[k]; od;
print(b); od; end: P(10^4,8);

roll[n_, b_] := Block[{w = IntegerDigits[n, b]}, Append[Rest@ w, First@ w]]; b = 8; FromDigits[#, b] & /@ (roll[#, b] & /@ Range[0, 69]) (* Michael De Vlieger, Mar 04 2015 *)

cp's OEIS Frontend

A378635 Triangle T(n,k) read by rows, where row n is a permutation of numbers 1 through n, such that if the deck of n cards is prepared in this order, and under-down dealing is used, then the resulting cards are put down in increasing order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A038572 a(n) = n rotated one binary place to the right.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A080079 Least number causing the longest carry sequence when adding numbers <= n to n in binary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Python

Formula

A062050 n-th chunk consists of the numbers 1, ..., 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A006165 a(1) = a(2) = 1; thereafter a(2n+1) = a(n+1) + a(n), a(2n) = 2a(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python