A227455 Sequence defined recursively: 1 is in the sequence, and k > 1 is in the sequence iff for some prime divisor p of k, p-1 is not in the sequence.

1, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 21, 23, 24, 25, 27, 29, 30, 33, 34, 35, 36, 39, 40, 42, 45, 46, 48, 50, 51, 53, 54, 55, 57, 58, 60, 63, 65, 66, 68, 69, 70, 72, 75, 78, 80, 81, 83, 84, 85, 87, 89, 90, 92, 93, 95, 96, 99, 100, 102, 105, 106, 108, 110

Offset

1,2

Comments

Consider a two-player game in which players take turns and a player given the position k = p_1^s_1 * ... * p_j^s_j must choose one of the j possible moves p_1 - 1, ..., p_j - 1, and the player's chosen move becomes the position given to the other player. The first player whose only possible move is 1 loses. Terms in this sequence are the winning positions for the player whose turn it is.

Links

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Example

Numbers of the form 2^k are not in the sequence because their unique prime divisor is p = 2 and p-1 = 1 is in the sequence.
Numbers of the form 3^k are in the sequence because 3-1 = 2 is not in the sequence.
Numbers of the form 5^k are in the sequence because 5-1 = 4 = 2^2, and 2 is not in the sequence.

Mathematica

fa=FactorInteger; win[1] = True; win[n_] := win[n] = ! Union@Table[win[fa[n][[i, 1]] - 1], {i, 1, Length@fa@n}] == {True}; Select[Range[300], win]

Prog

(Haskell)
a227455 n = a227455_list !! (n-1)
a227455_list = 1 : f [2..] [1] where
   f (v:vs) ws = if any (`notElem` ws) $ map (subtract 1) $ a027748_row v
                    then v : f vs (v : ws) else f vs ws
-- Reinhard Zumkeller, Dec 08 2014

Crossrefs

Cf. A227006, A227691, A027748.

Sequence in context: A187837 A325428 A239064 * A237417 A165740 A241571

Adjacent sequences: A227452 A227453 A227454 * A227456 A227457 A227458

Keyword

nonn

Author

José María Grau Ribas, Jul 12 2013

Extensions

Edited by Jon E. Schoenfield, Jan 23 2021

Status

approved