A005428 -id:A005428 - cp's OEIS frontend

A344792 a(n) is half the n-th term of a truncated sesquinary (base 3/2) tree.

1, 4, 2, 6, 10, 3, 13, 9, 22, 15, 121, 7, 5, 67, 20, 31, 14, 33, 76, 34, 23, 409, 182, 16, 11, 40, 8, 151, 101, 30, 46, 70, 47, 21, 49, 112, 50, 114, 172, 51, 175, 52, 35, 1381, 614, 273, 616, 24, 37, 25, 17, 60, 91, 12, 19, 340, 227, 769, 152, 45, 103, 69, 157

Offset: 1

John-Vincent Saddic, May 28 2021

The tree is created by planting a tree with alternating branching and nonbranching nodes (as described in A005428). The nodes are then labeled in order -- 1,2,3,4,... All odd nodes are removed, leaving an infinite binary tree of every even number. Finally, each node is divided by two. The first four rows of the resultant tree are as follows:
  1
  4   2
  6  10   3   13
  9  22  15  121  7  5  67  20
  ...
The first number of the n-th row, a(2^(n-1)), is A081614(n). The last number of the n-th row is A182459(n). The lowest number of the n-th row is A061419(n). It appears that when n is even, A189706(a(n)+1) = 0, and when n is odd A189706(a(n)+1) = 1. This is true for at least the first n = 1 through 40000.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
John-Vincent Saddic, Java code to produce the first n lines of the tree
John-Vincent Saddic, Diagram to construct the tree
John-Vincent Saddic, Log/log scatterplot
Index entries for sequences that are permutations of the natural numbers

Inverse is A345671.

Cf. A005428, A081614, A182459, A061419, A189706.

Java
```
See Links.
```

a:= proc(n) option remember;
      a(iquo(n, 2))*3 + irem(n, 2);
      while %::odd do ceil(% * 3/2) od; %/2
    end: a(1):=1:
seq(a(n), n=1..63);  # Alois P. Heinz, May 29 2021

a[n_] := a[n] = Module[{t}, t = a[Quotient[n, 2]]*3 + Mod[n, 2];
     While[OddQ[t], t = Ceiling[t * 3/2] ]; t/2]; a[1] = 1;
Table[a[n], {n, 1, 63}] (* Jean-François Alcover, Apr 14 2022, after Alois P. Heinz *)

a(n) = my(t=1); forstep(i=logint(n,2)-1,0,-1, t=3*t+1+bittest(n,i); my(k=valuation(t,2)); t=(t*3^k)>>(k+1)); t; \\ Kevin Ryde, May 29 2021

A079719 a(n) = n + floor(Sum_{k

Original entry on oeis.org

0, 1, 2, 4, 7, 12, 19, 29, 45, 68, 103, 156, 235, 353, 531, 797, 1197, 1796, 2695, 4044, 6067, 9101, 13653, 20480, 30721, 46083, 69125, 103689, 155534, 233302, 349954, 524932, 787399, 1181100, 1771651, 2657477, 3986217, 5979326, 8968990, 13453486

Offset: 0

Henry Bottomley, Feb 17 2003

			a(4) = 4+floor[(0+1+2+4)/2] = 4+floor[7/2] = 4+3 = 7

Harvey P. Dale, Table of n, a(n) for n = 0..1000

nxt[{n_,t_,a_}]:=Module[{c=n+1+Floor[t/2]},{n+1,t+c,c}]; NestList[nxt,{0,0,0},40][[All,3]] (* Harvey P. Dale, Aug 01 2021 *)

a(n)=A073941(n+4)-2 (and appears to be A005428(n+1)) =round[1.82505431574536323...*1.5^n - 2]

A348533 Generalized Josephus problem: Let T(m,k), k>=2, m=1,2,3,.., be the number of people on a circle such that the survivor is one of the first k-1 people after every k-th person has been removed.

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 8, 3, 2, 1, 16, 4, 3, 2, 1, 32, 6, 4, 3, 2, 1, 64, 9, 5, 4, 3, 2, 1, 128, 14, 7, 5, 4, 3, 2, 1, 256, 21, 9, 6, 5, 4, 3, 2, 1, 512, 31, 12, 8, 6, 5, 4, 3, 2, 1, 1024, 47, 16, 10, 7, 6, 5, 4, 3, 2, 1, 2048, 70, 22, 12, 8, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Gerhard Kirchner, Oct 21 2021

The table, see example, is read by ascending antidiagonals.

Trivial cases: T(m,k)=m for m

The recurrence in the formula section does not only yield T(m,k), but also the survivor's number S(m,k) so that the Josephus problem can be solved for any number N of people, especially for large N because T(m,k) grows exponentially, see link "Derivation of the recurrence", section II.

T(m,k) compared with other sequences ("->" means that the sequences can be made equal by removing repeated terms, see link "Derivation of the recurrence", section IV).

T(m,2) = A000079(m)=2^(m-1)

T(m,3) -> A073941

T(m,4) -> A072493

T(m+4,4)= A005427(m)

T(m,5) -> A120160

T(m,6) -> A120170

T(m,7) -> A120178

T(m,8) -> A120186

T(m,9) -> A120194

T(m,10)-> A120202

			k=4: 7 people, survivors number 2 <4.
k=4: 6 people, survivors number 5>=4, counterexample.
Table T(m,k) begins:
  m\k____2____3____4____5
   1:    1    1    1    1
   2:    2    2    2    2
   3:    4    3    3    3
   4:    8    4    4    4
   5:   16    6    5    5
   6:   32    9    7    6
   7:   64   14    9    8
   8:  128   21   12   10
   9:  256   31   16   12
  10:  512   47   22   15

Gerhard Kirchner, Derivation of the recurrence
Gerhard Kirchner, Table for 2<=k<=10 and 1<=m<=30
Index entries for sequences related to the Josephus Problem

Cf. A005428, A032434, A054995, A007495.

block(k:10, mmax:30, t:1, s:1, T:[1],
/*Terms T(m,k), m=1 thru mmax */
for m from 1 thru mmax-1 do(
    p:  mod(t, k-1),
    if s>p then e:-p else e:k-1-p,
    t: (k*t+e)/(k-1), s: 1+mod(s+e-1, t),
    T:append(T,[t])),
return (T));

Recurrence for T(m,k) and S(m,k), the survivor's number.
Start: T(1,k)=S(1,k)=1.
T(m+1,k)=(k*T(m,k)+e)/(k-1),
S(m+1,k)=1 + (S(m,k)+e-1) mod T(m+1,k),
with e=-p if S(m,k)>p and e=k-1-p otherwise, p = T(m,k) mod (k-1).

Previous Showing 21-23 of 23 results.

cp's OEIS Frontend

A344792 a(n) is half the n-th term of a truncated sesquinary (base 3/2) tree.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Java

Maple

Mathematica

PARI

A079719 a(n) = n + floor(Sum_{k

Views

Author

Keywords

Examples

Links

Programs

Mathematica

Formula

A348533 Generalized Josephus problem: Let T(m,k), k>=2, m=1,2,3,.., be the number of people on a circle such that the survivor is one of the first k-1 people after every k-th person has been removed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maxima

Formula