A171947 P-positions for game of UpMark.

1, 3, 7, 9, 11, 15, 19, 23, 25, 27, 31, 33, 35, 39, 41, 43, 47, 51, 55, 57, 59, 63, 67, 71, 73, 75, 79, 83, 87, 89, 91, 95, 97, 99, 103, 105, 107, 111, 115, 119, 121, 123, 127, 129, 131, 135, 137, 139, 143, 147, 151, 153, 155, 159, 161, 163, 167, 169, 171, 175, 179

Offset: 1

Author

N. J. A. Sloane, Oct 29 2010

Keywords

• nonn
• easy

Comments

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

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

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

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

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math. 312 (2012), no. 1, 42-46.

Crossrefs

Complement of A171946. Essentially identical to A072939.

A249034 gives missing odd numbers.

Cf. A003159.

Programs

Haskell

import Data.List (delete)
a171947 n = a171947_list !! (n-1)
a171947_list = 1 : f [2..] where
   f (w:ws) = y : f (delete y ws) where y = 2 * w - 1
-- Reinhard Zumkeller, Oct 26 2014

Maple

# Maple code for M+1 terms of sequence, from N. J. A. Sloane, Oct 26 2014
m:=1; a:=[m]; M:=100;
for n from 1 to M do
m:=m+1; if m in a then m:=m+1; fi;
c:=2*m-1;
a:=[op(a),c];
od:
[seq(a[n],n=1..nops(a))];

Mathematica

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 *)

Python

def A171947(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x):
        c, s = n+x-1, bin(x-1)[2:]
        l = len(s)
        for i in range(l&1,l,2):
            c -= int(s[i])+int('0'+s[:i],2)
        return c
    return bisection(f,n,n) # Chai Wah Wu, Jan 29 2025

Formula

Presumably equal to 2*A003159 + 1. - Reinhard Zumkeller, Oct 26 2014