OFFSET
1,2
COMMENTS
In "Divisor Nim", each player may only take a number of stones from a pile that is a proper divisor of the number of stones in that pile.
LINKS
Project Euler, Problem 509. Divisor Nim
FORMULA
a(n) = Sum_{0 <= a,b,c <= floor(log_2(n))} g(a, b, c), where g(a, b, c) = 0 if a XOR b XOR c = 0, else g(a, b, c) = f(a)*f(b)*f(c), and f(x) = floor(n/2^x) - floor(n/2^(x+1)).
EXAMPLE
Consider the position (4, 2, 1). A player may take 1 or 2 stones from the first pile; they may only take 1 stone from the second; and they can't take any stones from the third pile. The first player who can't make a valid move (i.e. all piles are of size one) loses.
PROG
(Python)
def a(n):
adicity = lambda k: int(n/2**k) - int(n/2**(k+1))
p2 = [0]
while True:
if 2**p2[-1] < n: p2.append(p2[-1]+1)
else: break
count = 0
for a in p2:
for b in p2:
for c in p2:
if a^b^c != 0:
count += adicity(a)*adicity(b)*adicity(c)
return count
CROSSREFS
KEYWORD
nonn
AUTHOR
Do Thanh Nhan, Apr 20 2025
STATUS
approved
