nayuki / project-euler-solutions

Runnable code for solving Project Euler problems in Java, Python, Mathematica, Haskell.

Project Euler solutions

A collection of Nayuki's program code to solve over 200 Project Euler math problems.

Every solved problem has a program written in Java and usually Python. Some solutions also have Mathematica and Haskell programs. Some solution programs include a detailed mathematical explanation/proof in the comments to justify the code's logic.

All problems from #1 to #100 have a Java and Python program, and problems #1 to #50 have a Mathematica program. This package contains at least 205 solutions in Java, at least 200 in Python, at least 125 in Mathematica, and at least 95 in Haskell.

Java solutions require JDK 9+. Python solutions are tested to work on CPython 3.9.6. Mathematica solutions are tested to work on Mathematica 5.1.

Home page with background info, table of solutions, benchmark timings, and more: https://www.nayuki.io/page/project-euler-solutions

---

Copyright © 2023 Project Nayuki. All rights reserved. No warranty.

This code is provided for reference only. You may republish any of this code verbatim with author and URL info intact.

You need written permission from the author to make modifications to the code, include parts into your own work, etc.

project-euler-solutions's Issues

Solution project Euler

suggestion

Incidentally, the solution to Problem 6 can be further simplified as the product of linear terms and a constant:

n(n-1)(n+1)(3n+2)/12

Issue with Problem 21 in Python

I ran the code for Problem 21 for the first ten numbers.

def compute():
	# Compute sum of proper divisors for each number
	divisorsum = [0] * 10
	for i in range(1, len(divisorsum)):
		for j in range(i * 2, len(divisorsum), i):
			divisorsum[j] += i
		# Find all amicable pairs within range
	ans = 0
	for i in range(1, len(divisorsum)):
		j = divisorsum[i]
		if j != i and j < len(divisorsum) and divisorsum[j] == i:
			ans += i
	return str(ans)

and it doesn't seem to return the right answer.

For example, for the first 10 numbers the pair (n, d(n)) (where d(n) = sum of proper divisors of n)
is:
[(2, 1), (3, 1), (5, 1), (7, 1), (4, 3), (9, 4), (6, 6), (8, 7), (10, 8)]
and the answer should be 17.

The code outputs: [0, 0, 1, 1, 3, 1, 6, 1, 7, 4] for divisorsum and
0 for the ans.

ReasonML solutions

Hi!

I'm solving the Project Euler problems with ReasonML, it's interesting to you if I open a PR with the solutions in this language into this repository?

License regarding Answers.txt

Are we allowed to include the Answers.txt file as-is in our own repos, thereby using it as reference material for testing self-written code?

Test of the GitHub issues system

testing123

add solutions using Julia language

thought it would be neat :)

project euler 80 python code

Import eulerlib module was not work

where is the code bro

[Question] Isn't it too slow to get answer?

https://github.com/nayuki/Project-Euler-solutions/blob/master/haskell/p010.hs

I did like your code. But it's too slow to get the answer.

Problem 27 - Theoretical Imporvement

Hello there, I think I found a theoretical vital time improvement to question 27 "Quadratic primes"
It relies on the following 2 lemmas:
1.If b is composite OR smaller then 0 then x^2+ax+b returns a non-prime number for x=0
Meaning that the prime sequence for those b already ends at x=0 [Note that in the examples 41 and 1601 are both bigger then 0 and prime]
This can remove both the negative numbers AND the composite numbers from the b search.
2.If prime p divides a and b then x^2+ax+b returns a composite number for x=p
[Trivial proof since p divides p^2+xp*p+yp]
for those ab pairs, the sequence end at most in x=p
That means we don't have to check the ab pairs which share a prime factor smaller then the minimum required consecutive sequence (which in our range is at least 39)

Crazy Magic, #26

Hi, I'm trying to understand what kind of crazy magic you're using for the twenty-sixth problem, specifically this little black box of black magic:

def reciprocal_cycle_len(n):
    seen = {}
    x = 1

    for i in itertools.count():
        if x in seen:
            return i - seen[x]
        else:
            seen[x] = i
            x = x * 10 % n

It's the simplest thing I've ever seen that I just can't figure out. I guess I'm just not good with numerology. Is there a spatial relationship that would make sense?

Puzzle 026 has wrong solition

Hi! Thank you for this repository. I use it frequently to check, whether my solutions are completely off the charts, in the right ballpark, or sane.

I believe however, that #026 might have a wrong solution. 1/171 has a recurring decimals length or 18, but 1/983 has a much longer sequence of recurring decimals: 982 digits long:

0 0 1 0 1 7 2 9 3 9 9 7 9 6 5 4 1 2 0 0 4 0 6 9 1 7 5 9 9 1 8 6 1 6 4 8 0 1 6 2 7 6 7 0 3 9 6 7 4 4 6 5 9 2 0 6 5 1 0 6 8 1 5 8 6 9 7 8 6 3 6 8 2 6 0 4 2 7 2 6 3 4 7 9 1 4 5 4 7 3 0 4 1 7 0 9 0 5 3 9 1 6 5 8 1 8 9 2 1 6 6 8 3 6 2 1 5 6 6 6 3 2 7 5 6 8 6 6 7 3 4 4 8 6 2 6 6 5 3 1 0 2 7 4 6 6 9 3 7 9 4 5 0 6 6 1 2 4 1 0 9 8 6 7 7 5 1 7 8 0 2 6 4 4 9 6 4 3 9 4 7 1 0 0 7 1 2 1 0 5 7 9 8 5 7 5 7 8 8 4 0 2 8 4 8 4 2 3 1 9 4 3 0 3 1 5 3 6 1 1 3 9 3 6 9 2 7 7 7 2 1 2 6 1 4 4 4 5 5 7 4 7 7 1 1 0 8 8 5 0 4 5 7 7 8 2 2 9 9 0 8 4 4 3 5 4 0 1 8 3 1 1 2 9 1 9 6 3 3 7 7 4 1 6 0 7 3 2 4 5 1 6 7 8 5 3 5 0 9 6 6 4 2 9 2 9 8 0 6 7 1 4 1 4 0 3 8 6 5 7 1 7 1 9 2 2 6 8 5 6 5 6 1 5 4 6 2 8 6 8 7 6 9 0 7 4 2 6 2 4 6 1 8 5 1 4 7 5 0 7 6 2 9 7 0 4 9 8 4 7 4 0 5 9 0 0 3 0 5 1 8 8 1 9 9 3 8 9 6 2 3 6 0 1 2 2 0 7 5 2 7 9 7 5 5 8 4 9 4 4 0 4 8 8 3 0 1 1 1 9 0 2 3 3 9 7 7 6 1 9 5 3 2 0 4 4 7 6 0 9 3 5 9 1 0 4 7 8 1 2 8 1 7 9 0 4 3 7 4 3 6 4 1 9 1 2 5 1 2 7 1 6 1 7 4 9 7 4 5 6 7 6 5 0 0 5 0 8 6 4 6 9 9 8 9 8 2 7 0 6 0 0 2 0 3 4 5 8 7 9 9 5 9 3 0 8 2 4 0 0 8 1 3 8 3 5 1 9 8 3 7 2 3 2 9 6 0 3 2 5 5 3 4 0 7 9 3 4 8 9 3 1 8 4 1 3 0 2 1 3 6 3 1 7 3 9 5 7 2 7 3 6 5 2 0 8 5 4 5 2 6 9 5 8 2 9 0 9 4 6 0 8 3 4 1 8 1 0 7 8 3 3 1 6 3 7 8 4 3 3 3 6 7 2 4 3 1 3 3 2 6 5 5 1 3 7 3 3 4 6 8 9 7 2 5 3 3 0 6 2 0 5 4 9 3 3 8 7 5 8 9 0 1 3 2 2 4 8 2 1 9 7 3 5 5 0 3 5 6 0 5 2 8 9 9 2 8 7 8 9 4 2 0 1 4 2 4 2 1 1 5 9 7 1 5 1 5 7 6 8 0 5 6 9 6 8 4 6 3 8 8 6 0 6 3 0 7 2 2 2 7 8 7 3 8 5 5 5 4 4 2 5 2 2 8 8 9 1 1 4 9 5 4 2 2 1 7 7 0 0 9 1 5 5 6 4 5 9 8 1 6 8 8 7 0 8 0 3 6 6 2 2 5 8 3 9 2 6 7 5 4 8 3 2 1 4 6 4 9 0 3 3 5 7 0 7 0 1 9 3 2 8 5 8 5 9 6 1 3 4 2 8 2 8 0 7 7 3 1 4 3 4 3 8 4 5 3 7 1 3 1 2 3 0 9 2 5 7 3 7 5 3 8 1 4 8 5 2 4 9 2 3 7 0 2 9 5 0 1 5 2 5 9 4 0 9 9 6 9 4 8 1 1 8 0 0 6 1 0 3 7 6 3 9 8 7 7 9 2 4 7 2 0 2 4 4 1 5 0 5 5 9 5 1 1 6 9 8 8 8 0 9 7 6 6 0 2 2 3 8 0 4 6 7 9 5 5 2 3 9 0 6 4 0 8 9 5 2 1 8 7 1 8 2 0 9 5 6 2 5 6 3 5 8 0 8 7 4 8 7 2 8 3 8 2 5 0 2 5 4 3 2 3 4 9 9 4 9 1 3 5 3

If we name that sequence s for "sequence", then 1/983 is:

0.sssss...

How are you calculating floor of a number

I saw you calculating sqrt of some number but I didn't get how you are calculating floor of that number in this code

def sqrt(x):
	assert x >= 0
	i = 1
	while i * i <= x:
		i *= 2
	y = 0
	while i > 0:
		if (y + i)**2 <= x:
			y += i
		i //= 2
	return y

Line 4

I was getting a syntax error on line:
NONPRIME_LAST_DIGITS = {0, 2, 4, 5, 6, 8}

Which I was able to "correct" by changing to an array notation [0,2...] on line:
if i == 1 or arr[-1] not in [0,2,4,5,6,8]:

Can you keep uploading?

there is around 900 problems at 2024

... is it okay to publish my solution elsewhere?

I've noticed that this repo posts most if not all of the Project Euler answers. That appears to go against the spirit of Project Euler. There is a write up near the bottom of the Project Euler FAQs that talks about this.