PY
py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
'''
I modified the list append method to work with 2 list. The purpose is to prevent the list from becoming too long. By switching between two lists, only the significant values are retained, keeping the list lengths at 2.
'''
def f(n):
if n==0 or n==1:
return 1
#use 2 lists to keep list len at 2
arr1 = [1,1]
arr2 = [1,1]
#alternate between arr1 and arr2
for i in range(2,n+1):
if i%2==0:
arr2[0] = arr1[1]
arr2[1] = (arr1[-1]**2 + arr1[-2]**2) % 47
else:
arr1[0] = arr2[1]
arr1[1] = (arr2[-1]**2 + arr2[-2]**2) % 47
#sanity check
#print(f'{arr1=}\n{arr2=}')
if n%2==0 and n>1:
return arr2[-1]
else:
return arr1[-1]
print('f({1000000}) =', f(1000000))
Enter to Rename, Shift+Enter to Preview
OUTPUT
Run