login
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.
5

%I #37 Jan 23 2021 23:36:40

%S 1,3,5,6,9,10,12,15,17,18,20,21,23,24,25,27,29,30,33,34,35,36,39,40,

%T 42,45,46,48,50,51,53,54,55,57,58,60,63,65,66,68,69,70,72,75,78,80,81,

%U 83,84,85,87,89,90,92,93,95,96,99,100,102,105,106,108,110

%N 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.

%C 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.

%H Reinhard Zumkeller, <a href="/A227455/b227455.txt">Table of n, a(n) for n = 1..10000</a>

%e 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.

%e Numbers of the form 3^k are in the sequence because 3-1 = 2 is not in the sequence.

%e Numbers of the form 5^k are in the sequence because 5-1 = 4 = 2^2, and 2 is not in the sequence.

%t 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]

%o (Haskell)

%o a227455 n = a227455_list !! (n-1)

%o a227455_list = 1 : f [2..] [1] where

%o f (v:vs) ws = if any (`notElem` ws) $ map (subtract 1) $ a027748_row v

%o then v : f vs (v : ws) else f vs ws

%o -- _Reinhard Zumkeller_, Dec 08 2014

%Y Cf. A227006, A227691, A027748.

%K nonn

%O 1,2

%A _José María Grau Ribas_, Jul 12 2013

%E Edited by _Jon E. Schoenfield_, Jan 23 2021