cp's OEIS Frontend

A171947 P-positions for game of UpMark.

%I A171947 #49 Apr 22 2025 04:00:26
%S A171947 1,3,7,9,11,15,19,23,25,27,31,33,35,39,41,43,47,51,55,57,59,63,67,71,
%T A171947 73,75,79,83,87,89,91,95,97,99,103,105,107,111,115,119,121,123,127,
%U A171947 129,131,135,137,139,143,147,151,153,155,159,161,163,167,169,171,175,179
%N A171947 P-positions for game of UpMark.
%C A171947 The following description, due to D. R. Hofstadter, Email, Oct 23 2014, is presumably equivalent to Fraenkel's. Begin with 1, and then each new member is 2k-1, where k is the smallest unused non-member of the sequence. Thus k starts out as 2, so 2k-1 = 3, so 3 is the sequence's second member. The next value of k is 4, giving 2k-1 = 7, so 7 is the sequence's third member. Then k = 5, so 9 is the next member. Then k = 6, so 11 is the next member. Then k = 8, so 15 is the next member. Etc. - _N. J. A. Sloane_, Oct 26 2014
%C A171947 It appears that this is the sequence of positions of 1 in the 1-limiting word of the morphism 0 -> 10, 1 -> 00; see A284948. - _Clark Kimberling_, Apr 18 2017
%C A171947 It appears that this sequence gives the positions of 0 in the limiting 0-word of the morphism 0 -> 11, 1 -> 01. See A285383. - _Clark Kimberling_, Apr 26 2017
%C A171947 It appears that this sequence gives integers that are congruent to 2^k+1 (mod 2^(k+1)), where k is any odd integer >=1. - _Jules Beauchamp_, Dec 04 2023
%H A171947 Reinhard Zumkeller, <a href="/A171947/b171947.txt">Table of n, a(n) for n = 1..10000</a>
%H A171947 Aviezri S. Fraenkel, <a href="http://dx.doi.org/10.1016/j.disc.2011.03.032">The vile, dopey, evil and odious game players</a>, Discrete Math. 312 (2012), no. 1, 42-46.
%F A171947 Presumably equal to 2*A003159 + 1. - _Reinhard Zumkeller_, Oct 26 2014
%p A171947 # Maple code for M+1 terms of sequence, from _N. J. A. Sloane_, Oct 26 2014
%p A171947 m:=1; a:=[m]; M:=100;
%p A171947 for n from 1 to M do
%p A171947 m:=m+1; if m in a then m:=m+1; fi;
%p A171947 c:=2*m-1;
%p A171947 a:=[op(a),c];
%p A171947 od:
%p A171947 [seq(a[n],n=1..nops(a))];
%t A171947 f[n_] := Block[{a = {1}, b = {}, k}, Do[k = 2; While[MemberQ[a, k] || MemberQ[b, k], k++]; AppendTo[a, 2 k - 1]; AppendTo[b, k], {i, 2, n}]; a]; f@ 120 (* _Michael De Vlieger_, Jul 20 2015 *)
%o A171947 (Haskell)
%o A171947 import Data.List (delete)
%o A171947 a171947 n = a171947_list !! (n-1)
%o A171947 a171947_list = 1 : f [2..] where
%o A171947    f (w:ws) = y : f (delete y ws) where y = 2 * w - 1
%o A171947 -- _Reinhard Zumkeller_, Oct 26 2014
%o A171947 (Python)
%o A171947 def A171947(n):
%o A171947     def bisection(f,kmin=0,kmax=1):
%o A171947         while f(kmax) > kmax: kmax <<= 1
%o A171947         kmin = kmax >> 1
%o A171947         while kmax-kmin > 1:
%o A171947             kmid = kmax+kmin>>1
%o A171947             if f(kmid) <= kmid:
%o A171947                 kmax = kmid
%o A171947             else:
%o A171947                 kmin = kmid
%o A171947         return kmax
%o A171947     def f(x):
%o A171947         c, s = n+x-1, bin(x-1)[2:]
%o A171947         l = len(s)
%o A171947         for i in range(l&1,l,2):
%o A171947             c -= int(s[i])+int('0'+s[:i],2)
%o A171947         return c
%o A171947     return bisection(f,n,n) # _Chai Wah Wu_, Jan 29 2025
%Y A171947 Complement of A171946. Essentially identical to A072939.
%Y A171947 A249034 gives missing odd numbers.
%Y A171947 Cf. A003159.
%K A171947 nonn,easy
%O A171947 1,2
%A A171947 _N. J. A. Sloane_, Oct 29 2010