A025480
a(2n) = n, a(2n+1) = a(n).
Original entry on oeis.org
0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19, 2, 20, 10, 21, 5, 22, 11, 23, 1, 24, 12, 25, 6, 26, 13, 27, 3, 28, 14, 29, 7, 30, 15, 31, 0, 32, 16, 33, 8, 34, 17, 35, 4, 36, 18, 37, 9, 38, 19, 39, 2, 40, 20, 41, 10
Offset: 0
From Deuard Worthen (deuard(AT)raytheon.com), Jan 27 2006: (Start)
The sequence can be constructed as a triangle as:
0
0 1
0 2 1 3
0 4 2 5 1 6 3 7
0 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15
...
At each stage we interleave the next 2^m numbers in the previous row. (End)
Left=0/1, Right=1/0: StB=A007305/A047679; Left=0/1, Right=1/1: StB=A007305/A007306; Left=1/3, Right=2/3: StB=A153161/A153162. - _Reinhard Zumkeller_, Dec 22 2008
- L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.
- N. J. A. Sloane, Table of n, a(n) for n = 0..10000
- Josef Eschgfäller and Andrea Scarpante, Dichotomic random number generators, arXiv:1603.08500 [math.CO], 2016.
- Ralf Hinze, Concrete stream calculus: An extended study, J. Funct. Progr. 20 (5-6) (2010) 463-535, doi, Section 3.2.4.
- L. Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
- Ralf Stephan, Some divide-and-conquer sequences ....
- Ralf Stephan, Table of generating functions.
- Paul Tarau, A Groupoid of Isomorphic Data Transformations, Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185, Springer, LNAI 5625.
- Index entries for sequences related to the Josephus Problem.
Cf.
A108202,
A138002,
A000265,
A003602,
A103391,
A153733,
A220466,
A225381,
A131987,
A263390,
A181391,
A007814.
-
import Data.List
interleave xs ys = concat . transpose $ [xs,ys]
a025480 = interleave [0..] a025480
-- Cale Gibbard, Nov 18 2009
-
Cf. comments by Worthen and Hasler.
import Data.List (transpose)
a025480 n k = a025480_tabf !! n !! k
a025480_row n = a025480_tabf !! n
a025480_tabf = iterate (\xs -> concat $
transpose [xs, [length xs .. 2 * length xs - 1]]) [0]
a025480_list = concat $ a025480_tabf
-- Reinhard Zumkeller, Apr 29 2012
-
A025480 := proc(n)
option remember ;
if type(n,'even') then
n/2 ;
else
procname((n-1)/2) ;
end if;
end proc:
seq(A025480(n),n=0..100) ; # R. J. Mathar, Jul 16 2020
-
a[n_] := a[n] = If[OddQ@n, a[(n - 1)/2], n/2]; Table[ a[n], {n, 0, 83}] (* Robert G. Wilson v, Mar 30 2006 *)
Table[BitShiftRight[n, IntegerExponent[n, 2] + 1], {n, 100}] (* IWABUCHI Yu(u)ki, Oct 13 2012 *)
-
a(n)={while(n%2,n\=2);n\2} \\ M. F. Hasler, May 03 2008
-
A025480(n)=n>>valuation(n*2+2,2) \\ M. F. Hasler, Apr 12 2012
-
def A025480(n): return n>>((~(n+1)&n).bit_length()+1) # Chai Wah Wu, Jul 13 2022
-
A025480 = lambda n: odd_part(n+1)//2
[A025480(n) for n in (0..83)] # Peter Luschny, May 20 2014
A321298
Triangle read by rows: T(n,k) is the number of the k-th eliminated person in the Josephus elimination process for n people and a count of 2, 1 <= k <= n.
Original entry on oeis.org
1, 2, 1, 2, 1, 3, 2, 4, 3, 1, 2, 4, 1, 5, 3, 2, 4, 6, 3, 1, 5, 2, 4, 6, 1, 5, 3, 7, 2, 4, 6, 8, 3, 7, 5, 1, 2, 4, 6, 8, 1, 5, 9, 7, 3, 2, 4, 6, 8, 10, 3, 7, 1, 9, 5, 2, 4, 6, 8, 10, 1, 5, 9, 3, 11, 7, 2, 4, 6, 8, 10, 12, 3, 7, 11, 5, 1, 9, 2, 4, 6, 8, 10, 12, 1, 5, 9, 13, 7, 3, 11, 2, 4, 6, 8, 10, 12, 14
Offset: 1
Triangle begins:
1;
2, 1;
2, 1, 3;
2, 4, 3, 1;
2, 4, 1, 5, 3;
2, 4, 6, 3, 1, 5;
2, 4, 6, 1, 5, 3, 7;
2, 4, 6, 8, 3, 7, 5, 1;
2, 4, 6, 8, 1, 5, 9, 7, 3;
2, 4, 6, 8, 10, 3, 7, 1, 9, 5;
2, 4, 6, 8, 10, 1, 5, 9, 3, 11, 7;
2, 4, 6, 8, 10, 12, 3, 7, 11, 5, 1, 9;
2, 4, 6, 8, 10, 12, 1, 5, 9, 13, 7, 3, 11;
...
For n = 5, to get the entries in 5th row from left to right, start with (^1, 2, 3, 4, 5) and the pointer at position 1, indicated by the caret. 1 is skipped and 2 is eliminated to get (1, ^3, 4, 5). (The pointer moves ahead to the next "live" number.) On the next turn, 3 is skipped and 4 is eliminated to get (1, 3, ^5). Then 1, 5, and 3 are eliminated in that order (going through (^3, 5) and (^3)). This gives row 5 of the triangle and entries a(11) through a(15) in this sequence.
The right border of this triangle is
A006257.
-
Table[Rest@ Nest[Append[#1, {Delete[#2, #3 + 1], #2[[#3 + 1]], #3}] & @@ {#, #[[-1, 1]], Mod[#[[-1, -1]] + 1, Length@ #[[-1, 1]]]} &, {{Range@ n, 0, 0}}, n][[All, 2]], {n, 14}] // Flatten (* Michael De Vlieger, Nov 13 2018 *)
-
def A321298(n,k):
if 2*k<=n: return 2*k
n2,r=divmod(n,2)
if r==0: return 2*A321298(n2,k-n2)-1
if k==n2+1: return 1
return 2*A321298(n2,k-n2-1)+1 # Pontus von Brömssen, Sep 18 2022
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.
Original entry on oeis.org
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
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;
A380201
Triangle T(n,k) read by rows, where row n is a permutation of numbers 1 through n, such that if a deck of n cards is prepared in this order, and SpellUnder-Down dealing is used, then the resulting cards are put down in increasing order.
Original entry on oeis.org
1, 2, 1, 1, 3, 2, 2, 4, 3, 1, 5, 3, 2, 1, 4, 4, 2, 5, 1, 3, 6, 2, 3, 4, 1, 6, 5, 7, 5, 6, 8, 1, 7, 4, 3, 2, 6, 5, 4, 1, 9, 3, 8, 2, 7, 4, 9, 10, 1, 3, 6, 8, 2, 5, 7, 6, 7, 3, 1, 11, 5, 8, 2, 10, 4, 9, 10, 3, 5, 1, 11, 12, 7, 2, 4, 6, 8, 9, 3, 8, 7, 1, 11, 6, 4, 2, 12, 13, 10, 9, 5, 12, 10, 6, 1, 13, 4, 9, 2, 14, 8, 11, 5
Offset: 1
Triangle begins:
1;
2, 1;
1, 3, 2;
2, 4, 3, 1;
5, 3, 2, 1, 4;
4, 2, 5, 1, 3, 6;
2, 3, 4, 1, 6, 5, 7;
5, 6, 8, 1, 7, 4, 3, 2;
...
For n = 4 suppose there are four cards arranged in order 2, 4, 3, 1. Three cards go under for each letter in O-N-E, then 1 is dealt. Now the deck is ordered 2,4,3. Three cards go under for each letter in T-W-O, then card 2 is dealt. Now the leftover deck is ordered 4,3. Five cards go under for each letter in T-H-R-E-E, then card 3 is dealt. Finally, card 4 is dealt. The dealt cards are in numerical order. Thus, the fourth row of the triangle is 2, 4, 3, 1.
Cf.
A005589,
A006257,
A225381,
A321298,
A378635,
A380201,
A380202,
A380204,
A380246,
A380247,
A380248.
-
from num2words import num2words as n2w
def spell(n):
return sum(1 for c in n2w(n).replace(" and", "").replace(" ", "").replace(",","").replace("-", ""))
def nthRow(n):
l = []
for i in range(0,n):
l.append(0)
zp = 0
for j in range(1,n+1):
zc = 0
while zc <= spell(j):
if l[zp] == 0:
zc += 1
zp += 1
zp = zp % n
l[zp-1] = str(j)
return l
l = []
for i in range(1,20):
l += nthRow(i)
print(", ".join(l))
A380204
A version of the Josephus problem: a(n) is the surviving integer under the spelling version of the elimination process.
Original entry on oeis.org
1, 1, 2, 2, 1, 6, 7, 3, 5, 3, 5, 6, 10, 9, 2, 13, 3, 16, 10, 2, 15, 6, 15, 6, 21, 1, 7, 23, 26, 6, 20, 12, 27, 29, 7, 2, 36, 11, 6, 7, 32, 6, 32, 43, 10, 31, 7, 5, 42, 1, 17, 48, 7, 31, 53, 25, 42, 43, 29, 39, 51, 25, 43, 7, 26, 59, 15, 10, 60, 69, 13, 57, 54, 66, 57, 30, 9, 35, 64, 9, 65, 1, 15, 3, 79, 47, 86, 7
Offset: 1
Consider n = 4 people. The first person eliminated is number 4. This leaves the remaining people in the order 1, 2, 3. The second person eliminated is number 1; the people left are in the order 2, 3. The next person eliminated is numbered 3, leaving only the person numbered 2. Thus a(4) = 2.
-
from num2words import num2words as n2w
def f(n): return sum(1 for c in n2w(n).replace(" and", "") if c.isalpha())
def a(n):
c, i, J = 1, 0, list(range(1, n+1))
while len(J) > 1:
i = (i + f(c))%len(J)
q = J.pop(i)
c = c+1
return J[0]
print([a(n) for n in range(1, 89)]) # Michael S. Branicky, Jan 26 2025
A380246
Elimination order of the first person in a variation of the Josephus problem, where the number of skipped people correspond to the number of letters in consecutive numbers, called SpellUnder-Down.
Original entry on oeis.org
1, 2, 1, 2, 5, 4, 2, 5, 6, 4, 6, 10, 3, 12, 6, 8, 15, 4, 13, 19, 14, 17, 5, 22, 18, 26, 6, 20, 13, 17, 19, 23, 7, 25, 21, 31, 22, 32, 8, 31, 38, 20, 29, 9, 27, 18, 43, 10, 15, 50, 37, 20, 16, 41, 11, 21, 39, 36, 34, 32, 29, 12, 36, 50, 27, 53, 35, 19, 45, 67, 13, 20, 70, 59, 74, 26, 21, 40, 65, 14, 49, 82, 33, 43, 28, 34, 53, 15
Offset: 1
Consider n = 4 people. The first person eliminated is number 4. This leaves the remaining people in order 1, 2, 3. The second person eliminated is number 1. Thus, person number 1 is eliminated in the second round, implying that a(4) = 2.
Cf.
A005589,
A006257,
A225381,
A321298,
A378635,
A380201,
A380202,
A380204,
A380246,
A380247,
A380248.
-
from num2words import num2words as n2w
def spell(n):
return sum(1 for c in n2w(n).replace(" and", "").replace(" ", "").replace(chr(44), "").replace("-", ""))
def nthRow(n):
l = []
for i in range(0,n):
l.append(0)
zp = 0
for j in range(1,n+1):
zc = 0
while zc <= spell(j):
if l[zp] == 0:
zc += 1
zp += 1
zp = zp % n
l[zp-1] = str(j)
return l
l = []
for i in range(1,89):
l += [nthRow(i)[0]]
print(l)
-
from num2words import num2words as n2w
def f(n): return sum(1 for c in n2w(n).replace(" and", "") if c.isalpha())
def a(n):
c, i, J = 1, 0, list(range(1, n+1))
while len(J) > 0:
i = (i + f(c))%len(J)
q = J.pop(i)
if q == 1: return c
c = c+1
print([a(n) for n in range(1, 89)]) # Michael S. Branicky, Feb 15 2025
A380202
Number of card moves to deal n cards using the SpellUnder-Down dealing.
Original entry on oeis.org
4, 8, 14, 19, 24, 28, 34, 40, 45, 49, 56, 63, 72, 81, 89, 97, 107, 116, 125, 136, 146, 156, 168, 179, 190, 200, 212, 224, 235, 246, 256, 266, 278, 289, 300, 310, 322, 334, 345, 355, 364, 373, 384, 394, 404, 413, 424, 435, 445, 455, 464, 473, 484, 494, 504, 513, 524, 535, 545, 555, 564, 573, 584, 594, 604, 613, 624, 635, 645
Offset: 1
The dealing pattern to deal three cards is UUUDUUUDUUUUUD. It contains 14 letters, thus, a(3) = 14.
Cf.
A005589,
A006257,
A067278,
A225381,
A321298,
A378635,
A380201,
A380204,
A380246,
A380247,
A380248.
A380247
Triangle read by rows: T(n,k) is the number of the k-th eliminated person in the variation of the Josephus elimination process for n people, where the number of people skipped correspond to the number of letters in the next number in English alphabet.
Original entry on oeis.org
1, 2, 1, 1, 3, 2, 4, 1, 3, 2, 4, 3, 2, 5, 1, 4, 2, 5, 1, 3, 6, 4, 1, 2, 3, 6, 5, 7, 4, 8, 7, 6, 1, 2, 5, 3, 4, 8, 6, 3, 2, 1, 9, 7, 5, 4, 8, 5, 1, 9, 6, 10, 7, 2, 3, 4, 8, 3, 10, 6, 1, 2, 7, 11, 9, 5, 4, 8, 2, 9, 3, 10, 7, 11, 12, 1, 5, 6, 4, 8, 1, 7, 13, 6, 3, 2, 12, 11, 5, 9, 10, 4, 8, 14, 6, 12, 3, 13, 10, 7, 2, 11, 1, 5, 9, 4
Offset: 1
Triangle begins:
1;
2, 1;
1, 3, 2;
4, 1, 3, 2;
4, 3, 2, 5, 1;
4, 2, 5, 1, 3, 6;
4, 1, 2, 3, 6, 5, 7;
...
For n = 4 suppose four people are arranged in a circle corresponding to the fourth row of the triangle. Three people are skipped for each letter in O-N-E; then the 4th person is eliminated. This means the row starts with 4. The next three people are skipped, and the person eliminated is number 1. Thus, the next element in the row is 1. Then, 5 people are skipped, and the next person eliminated is number 3. Similarly, the last person eliminated is number 2. Thus, the fourth row of this triangle is 4, 1, 3, 2.
-
from num2words import num2words as n2w
def spell(n):
return sum(1 for c in n2w(n).replace(" and", "").replace(" ", "").replace(chr(44), "").replace("-", ""))
def inverse_permutation(p):
inv = [0] * len(p)
for i, x in enumerate(p):
inv[x-1] = i +1
return inv
def nthRow(n):
l = []
for i in range(0,n):
l.append(0)
zp = 0
for j in range(1,n+1):
zc = 0
while zc <= spell(j):
if l[zp] == 0:
zc += 1
zp += 1
zp = zp % n
l[zp-1] = j
return l
l = []
for i in range(1,15):
l += inverse_permutation(nthRow(i))
print(l)
-
from num2words import num2words as n2w
def f(n): return sum(1 for c in n2w(n).replace(" and", "") if c.isalpha())
def row(n):
c, i, J = 1, 0, list(range(1, n+1))
out = []
while len(J) > 1:
i = (i + f(c))%len(J)
q = J.pop(i)
out.append(q)
c = c+1
out.append(J[0])
return out
print([e for n in range(1, 15) for e in row(n)]) # Michael S. Branicky, Feb 15 2025
A380248
The order of the 13 cards of one suit such that after the SpellUnder-Down deal the cards are in order; a(n) is the n-th card in the deck.
Original entry on oeis.org
3, 8, 7, 1, 12, 6, 4, 2, 11, 13, 10, 9, 5
Offset: 1
The first card dealt is the fourth card in the deck, thus, the fourth card must be an ace.
A337191
A version of the Josephus problem: a(n) is the surviving integer under the skip-eliminate-eliminate version of the elimination process.
Original entry on oeis.org
1, 1, 1, 4, 4, 1, 7, 4, 1, 7, 4, 10, 7, 13, 10, 16, 13, 1, 16, 4, 19, 7, 22, 10, 25, 13, 1, 16, 4, 19, 7, 22, 10, 25, 13, 28, 16, 31, 19, 34, 22, 37, 25, 40, 28, 43, 31, 46, 34, 49, 37, 52, 40, 1, 43, 4, 46, 7, 49, 10, 52, 13, 55, 16, 58, 19, 61, 22, 64, 25, 67
Offset: 1
Consider 4 people in a circle in order 1,2,3,4. In the first round, person 1 is skipped and persons 2 and 3 are eliminated. Now people are in order 4,1. In the second round, person 4 is skipped and person 1 is eliminated. Person 4 is freed. Thus, a(4) = 4. - _Tanya Khovanova_, Apr 14 2025
-
nxt[{n_,a_,b_}]:={n+1,b,If[Mod[a+3,n+1]!=0,Mod[a+3,n+1],n+1]}; NestList[nxt,{2,1,1},70][[;;,2]] (* Harvey P. Dale, Jul 27 2024 *)
-
a(n) = if (n <= 2, 1, my(x = (a(n-2) + 3) % n); if (x, x, n)); \\ Michel Marcus, Aug 20 2020
-
a(n) = if (n<=1, return(1)); my(v=vector(n, i, i), w); while (#v > 3, if (#v <=3, w = [], w = vector(#v-3, k, v[k+3])); w = concat(w, Vec(v, 1)); v = w;); v[1]; \\ Michel Marcus, Mar 25 2025
Showing 1-10 of 39 results.
Comments