|
|
A308432
|
|
Given n cards in a stack numbered from 1 to n with 1 at the top, repeat the following process: first remove the card that is in the middle (at position (size of the stack)/2, rounding up), then move the card that is at the bottom of the stack to the top. This process is repeated until there is only one card left. a(n) is the number of the last remaining card.
|
|
1
|
|
|
1, 2, 1, 4, 4, 4, 3, 2, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
a(n) = 1 if n is a power of 3.
a(n) = n if n-1 is a power of 3.
Theorem: Formula below describes the sequence.
Proof: a(n-1) gives the final card from a deck of size n-1, so a(n) will be equal to whichever card occupies the a(n-1)-th position after one iteration. If a(n-1) = 1, this will be card n, if a(n-1) <= ceiling(n/2), this will be card a(n-1)-1, and otherwise it will be card a(n-1). If a(3^k) = 1 (true for k = 0), then for this k:
a(n) = 3^k + 1 for 3^k + 1 <= n <= 2*3^k,
a(n) = 3^(k+1) + 1 - n for 2*3^k + 1 <= n <= 3^(k+1),
and thus a(3^(k+1)) = 1, so the formula holds for all k. (End)
|
|
LINKS
|
|
|
FORMULA
|
Let t = 3^floor(log_3(n)); then
a(n) = 1 if n = t,
t + 1 if n <= 2*t and n != t,
3*t - n + 1 otherwise.
|
|
PROG
|
(C)
//pow3 is a vector where pow3[n] = 3^n
int f(int n){
int x = 0;
while(pow3[x+1] <= n) x++;
return x;
}
int a(int n){
int fn = f(n);
if(n == pow3[fn]){
return 1;
}else if(n<=(pow3[fn]<<1) && n!=pow3[fn]){
return pow3[fn]+1;
}else{
return pow3[fn+1] - (n-1);
}
}
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|