import numpy as np;
def is_prime(x):
test = False;
for j in range(2,int(np.sqrt(x)) + 1):
if x%j == 0:
return test;
test = True;
return test;
def primes_list(x):
plist=np.zeros(x,dtype=int);
k=2;
count=0;
while count<x:
if is_prime(k):
plist[count] = k;
count += 1;
k += 1;
return plist[-1];
N = 10001;
print(primes_list(N))
I just did it a silly way, to get the answer 
I don’t really want to compete with anyone just see what other people did, and if they optimised then cool
Edit:
oh that place. Yeah I can’t imagine I want to compete with people there.
Maybe if the problem was more well defined on what one should optimize. Again as mentioned the quickest method is just to google the prime or ask wolfram etc and then have your function just return that number 
Oh wait what? So there is a sub-ns solution for the primes thing??
executed in nanoseconds
Is also fairly ambiguous. Maybe we could do a bruteforce solution in picoseconds on a quantum architecture.
My code is as always not pretty, but mathematically efficient, it runs O(n*log(n))
def isPrime(n,primes):
i = j = 0
while primes[j] < math.sqrt(n):
j += 1
for i in range(j+1):
if (n/primes[i]).is_integer():
return primes
i += i
primes.append(n)
return primes
def getNthPrime(n):
primes = [2]
i = 3
while len(primes) < n:
primes = isPrime(i,primes)
i += 1
return primes.pop()
print(getNthPrime(10001))
I just noticed Euler website has a… friend(?) feature. It seems you can add friend and view others’ progress I guess? Not very proud of my progress but anyone want to be friend? 
1682596_77PAA3iS7ehWOOH8CFjOg4sICwzL18qV
I added you @Chinitsu. I guess it works unilaterally, if I know your key?
Here is my key if anyone wants to add me:
223131_BkWlWOSSFDYhQy35ojrqWpQx6fiZIDzl
How do you get O(nlogn)?
if the number of primes below N is asymptotically N/log(N), it seems like isPrime() will be O(sqrt(N)/log(N)), and therefore the overall algorithm will be O(N^(3/2) / log(N))
there could totally be some sum identity I’m missing here, that’s why I’m asking
Ah, yes you are 100% right, I was daydreaming.
But pragmatically, O(sqrt(n)/log(n)) is as ‘only a tiny bit’ worse than O(log(n)) as it gets 
In fact, for the ln, for 10’001, sqrt(n)/ln(n) is a more conservative bound than ln(n).
Oh hey @Yebellz I noticed you also did the #81, #82, #83 chain. Did you happen to use A* too?
Any interest in #7 or possibly #8 @bugcat?
I’m reading #8 and I can’t even understand it.
Not sure yet if I understand it correctly:
So they have that 1000-digits number. And they just pick 4 adjacent digits in that number, calculate their product. The 4 digits picked that way with highest product is 9989.
Not they want us to do the same thing but with 13 adjacent digits instead of 4.
Basically you are supposed to slide a running window of 13 digits across that long number to detect when the product becomes maximal.
The general question would be, for any very large number, what is the n-digit window with the highest product.
Sure we’ll post #8 anyway:
The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
Yeah it’s this I think . Just run over the big number and multiply the digits and find the biggest product of those digits.
N = "73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450";
max_prod = 0;
for j in range(0,len(N)-12):
test = N[j:j+13];
test_prod = 1;
for k in test:
test_prod *= int(k);
max_prod = max(test_prod,max_prod);
print(max_prod)
I did learn how to break up really long lines of code though
I still find starting indexes at zero very confusing.
Oh I see.
Are you a lua programmer?
const biggestProductOf = (digitNo) =>
Array.from({ length: numberArr.length - digitNo }, (_, i) => i).reduce(
(max, i) =>
Math.max(
max,
numberArr.slice(i, i + digitNo).reduce((prod, curr) => prod * curr, 1)
)
);
console.log(biggestProductOf(13));
eslint
Devil’s spawn.
I’m not a programmer no. I don’t think I’ve looked at lua before no.
I’ll redact that, zero indexing is fine, swapping between the two is the confusing part It probably does make more sense in some ways.
I made some brief remarks about those problems, as well as the related problems 18 and 67, above:
I did not use A*, but instead a more basic dynamic programming solution. I wanted to make the coding as simple as possible, and don’t even bother recording the best path, but just the best cost.
Problem 81, like problems 18 and 67, are notably easier than the rest, since one just needs to do a single forward sweep through the graph, to incrementally compute the best cost to each node.
The solutions for both problems use the same code, but just take different inputs, i.e., run with python filename.py p018_triangle.txt or python filename.py p067_triangle.txt
import fileinput
import numpy as np
values = []
for line in fileinput.input():
line = [int(i) for i in line.rstrip().split(' ')]
values.append(np.asarray(line))
for i in range(1, len(values)):
previous = values[i - 1]
left = np.concatenate((previous, [0]))
right = np.concatenate(([0], previous))
best = np.maximum(left, right)
values[i] = values[i] + best
print(np.max(values[i]))
import numpy as np
costs = np.genfromtxt('p081_matrix.txt', delimiter=',')
total = np.zeros((80, 80))
for row in range(80):
for col in range(80):
if row == 0 and col == 0:
total[row, col] = costs[row, col]
elif row == 0:
total[row, col] = costs[row, col] + total[row, col - 1]
elif col == 0:
total[row, col] = costs[row, col] + total[row - 1, col]
else:
a = costs[row, col] + total[row - 1, col]
b = costs[row, col] + total[row, col - 1]
total[row, col] = a if a < b else b
print(total[79, 79])
On the other hand, my solutions for problems 82 and 83 perform iterative updates. When one node’s best cost is updated, it marks the neighboring nodes to be rechecked in the next iteration. In practice, it converged rather quickly to the optimal costs.
import numpy as np
SIZE = 80 # use smaller values to truncate the problem for testing
costs = np.genfromtxt('p082_matrix.txt', delimiter=',')[:SIZE, :SIZE]
# costs = np.genfromtxt('p082_test.txt', delimiter=',')[:SIZE, :SIZE]
total = float('inf') * np.ones((SIZE, SIZE))
print(costs)
def update(row, col):
best = total[row, col]
cost = costs[row, col]
if row > 0:
above = total[row - 1, col]
if above + cost < best:
best = above + cost
if row < SIZE - 1:
below = total[row + 1, col]
if below + cost < best:
best = below + cost
if col > 0:
left = total[row, col - 1]
if left + cost < best:
best = left + cost
check[row, col] = 0
if best < total[row, col]:
total[row, col] = best
if row > 0:
check[row - 1, col] = 1
if row < SIZE - 1:
check[row + 1, col] = 1
if col < SIZE - 1:
check[row, col + 1] = 1
total[:, 0] = costs[:, 0]
check = np.ones((SIZE, SIZE))
iterations = 0
while(np.sum(check) > 0):
iterations += 1
for i in range(SIZE):
for j in range(SIZE):
if check[i, j] > 0:
update(i, j)
print(iterations)
print(total)
print(np.min(total[:, SIZE - 1]))
import numpy as np
SIZE = 80 # use smaller values to truncate the problem for testing
costs = np.genfromtxt('p083_matrix.txt', delimiter=',')[:SIZE, :SIZE]
# costs = np.genfromtxt('p082_test.txt', delimiter=',')[:SIZE, :SIZE]
total = float('inf') * np.ones((SIZE, SIZE))
print(costs)
def update(row, col):
best = total[row, col]
cost = costs[row, col]
if row > 0:
above = total[row - 1, col]
if above + cost < best:
best = above + cost
if row < SIZE - 1:
below = total[row + 1, col]
if below + cost < best:
best = below + cost
if col > 0:
left = total[row, col - 1]
if left + cost < best:
best = left + cost
if col < SIZE - 1:
right = total[row, col + 1]
if right + cost < best:
best = right + cost
check[row, col] = 0
if best < total[row, col]:
total[row, col] = best
if row > 0:
check[row - 1, col] = 1
if row < SIZE - 1:
check[row + 1, col] = 1
if col > 0:
check[row, col - 1] = 1
if col < SIZE - 1:
check[row, col + 1] = 1
total[0, 0] = costs[0, 0]
check = np.ones((SIZE, SIZE))
iterations = 0
while(np.sum(check) > 0):
iterations += 1
for i in range(SIZE):
for j in range(SIZE):
if check[i, j] > 0:
update(i, j)
print(iterations)
print(total)
print(total[-1, -1])