82 lines
1.9 KiB
Python
82 lines
1.9 KiB
Python
from math import floor
|
|
from time import time_ns
|
|
|
|
|
|
def d(_num: int, den: int, n: int) -> int:
|
|
""" (10^n // d) % 10 -> (10^n % 10*d) // d % 10 """
|
|
return pow(10, n, 10 * den) // den % 10
|
|
|
|
|
|
def d_naiv(num: int, den: int, n: int, debug: bool = False) -> int:
|
|
"""Return the nth digit of the factional part of num / den."""
|
|
if num == den:
|
|
if debug:
|
|
print("1.0")
|
|
return 0
|
|
assert num < den
|
|
if debug:
|
|
print("0.", end="")
|
|
|
|
x = None
|
|
r = 0
|
|
i = 0
|
|
num *= 10 # 0.
|
|
nums = {}
|
|
while i < n:
|
|
if num == 0:
|
|
r = 0
|
|
break
|
|
elif num < den:
|
|
r = 0
|
|
if debug:
|
|
print(0, end="")
|
|
else:
|
|
r = num // den
|
|
num %= den
|
|
if debug:
|
|
print(r, end="")
|
|
i += 1
|
|
if x is None:
|
|
if num in nums:
|
|
j = nums[num]
|
|
delta = i - j
|
|
x = floor((n - i) / delta)
|
|
if debug:
|
|
print("---")
|
|
print(f"{den=} {j} -> {i} (d={delta} mult={x})")
|
|
print(f"\n{j} -{delta} {x}> {i} ")
|
|
i += x * delta
|
|
else:
|
|
nums[num] = i
|
|
num *= 10
|
|
if debug:
|
|
print()
|
|
# dr = (10**n % (10*den)) // den
|
|
dr = pow(10, n, 10 * den) // den
|
|
assert r == dr
|
|
# print(f"k = {den} n= {n}")
|
|
return r
|
|
|
|
|
|
def s(n: int) -> int:
|
|
return sum(d(1, k, n) for k in range(1, n + 1))
|
|
|
|
|
|
def euler_820():
|
|
d(1, 7, 10)
|
|
assert d(1, 2, 7) == 0
|
|
assert d(1, 3, 7) == 3
|
|
assert d(1, 5, 7) == 0
|
|
assert d(1, 6, 7) == 6
|
|
assert d(1, 7, 7) == 1
|
|
assert s(7) == 10
|
|
assert s(100) == 418
|
|
assert s(10000) == 43742
|
|
return s(10**7)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solution = euler_820()
|
|
print(f"e820.py: {solution}")
|
|
assert solution == 44967734
|