Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Columns 0,1 OR naively solution in Clear category for Exploring Wythoff Array by Phil15
import itertools as it
from math import sqrt
PHI = (1 + sqrt(5)) / 2
def wythoff_array(nb: int) -> tuple[int, int]:
# If first column: int(int(x * PHI) * PHI) == nb
# Then: nb / PHI ** 2 <= x < ((nb + 1) / PHI + 1) / PHI
for x in range(int(nb / PHI ** 2), int(((nb + 1) / PHI + 1) / PHI) + 1):
if int(int(x * PHI) * PHI) == nb:
return x - 1, 0
# Optionally here, as it is not required to currently pass tests:
# If second column: int(int(x * PHI) * PHI ** 2) == nb
# Then: nb / PHI ** 3 <= x < ((nb + 1) / PHI ** 2 + 1) / PHI
for x in range(int(nb / PHI ** 3), int(((nb + 1) / PHI ** 2 + 1) / PHI) + 1):
if int(int(x * PHI) * PHI ** 2) == nb:
return x - 1, 1
# Or go naively...
seen = set()
c = 1 # the minimal unseen number
a, b = 1, 2
for row in it.count():
for col, num in enumerate(fibonacci(a, b)):
if num > nb:
break
if num == nb:
return row, col
seen.add(num)
c = next(it.filterfalse(seen.__contains__, it.count(c)))
a, b = c, b + 3 + 2 * (c - a != 2)
def fibonacci(u, v):
yield u
yield v
while True:
u, v = v, u + v
yield v
if __name__ == '__main__':
assert wythoff_array(21) == (0, 6)
assert wythoff_array(47) == (1, 5)
assert wythoff_array(1_042) == (8, 8)
assert wythoff_array(424_242) == (9_030, 6)
assert wythoff_array(39_088_169) == (0, 36)
assert wythoff_array(39_088_170) == (14_930_352, 0)
print("Well done!")
Aug. 5, 2023
Comments:
