|
|
A334473
|
|
The n-cowboy shootout problem: a(3^k) = 3^k, a((3^k)+b) = b if (3^k)+b <= 2*3^k, otherwise a((3^k)+b) = 2*b-3^k, where b is a positive integer.
|
|
1
|
|
|
1, 1, 3, 1, 2, 3, 5, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 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, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Arrange n cowboys in a circle, each takes it in turn to shoot the cowboy directly opposite them, so there is only one cowboy shooting at a time. If there is a gap directly opposite them, because the number of remaining cowboys is odd, they shoot the cowboy on the left of the gap. Turns progress clockwise from the starting cowboy. Every time a cowboy is killed the circle is rearranged so every cowboy is evenly spaced.
a(n) is the starting position of the surviving cowboy.
A variant of the Josephus problem.
|
|
LINKS
|
|
|
EXAMPLE
|
a(4) = 1: The first cowboy shoots the 3rd cowboy opposite him. The 2nd cowboy would then be aiming in a gap between the 1st and the 4th cowboy so shoots the cowboy on the left of the gap (the 4th cowboy). We are now back with the 1st cowboy who shoots the only remaining cowboy (the 2nd) so wins.
|
|
PROG
|
(Python 3)
def highest_power_of_3(n):
option = 0
while 3**option <= n:
option +=1
return 3 ** (option -1)
def answer(n):
x = highest_power_of_3(n)
if x == n:
return x
else:
if n < 2 * x:
return n%x
else:
return x + 2 * (n%x)
number_of_terms = 100
answers = []
for i in range(1, number_of_terms + 1):
answers.append(answer(i))
print(answers)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|