Project Euler solutions

Solutions for problems 1 to ~100. Using Typescript, Golang and Python.

---

---

Usage

• Typescript:
  • Clone this repo;
  • $ yarn install to install dependencies;
  • $ npm t on typescript folder to run automated tests (Mocha + Chai)

---

Further reading

• Problem 10 - About primes. Also on how to optimize
• Problem 14 (Collatz Problem) - The Collatz Conjecture
• Problem 15 - Try different approaches such as Pascal Triangle
  • Or try different approaches
• Problem 18/67 - It uses Dynamic Programming (breaking problem into subproblems)
  • See these approaches, also see optimal substructures, graph theory and greedy algorithms.
• Problem 21 - Amicable numbers
• Problem 22 - Using Base36 to find the numeric position of each char.

Prime numbers

• Polinomial expressions that generate primes
• A005846 on OEIS (See problem 27).

---

Glossary

• Proper Divisor - Positive divisor of a number N, excluding N itself (source)

  Positive divisors of 3 = [1]
  Positive divisors of 8 = [1, 2, 4]
  

• Identity - An identity is a mathematical relationship equating one quantity to another (which may initially appear to be different). (source)

---

Notes

• Some exercises used typescript/ts-node, hence the packages.json
• Some JS/TS files use IIFEs (Immediately Invoked Function Expression) to avoid function and variable collision
• Problem 23
  • There are 6965 abundant numbers <= 28123, of which only 62 are uneven

---

Benchmarking

Just benchmarking data for possible optimization of algorithms.

• Problem 7

  • First solution takes ~11 seconds to execute
  • Refactored code takes ~10 miliseconds (~1000 times faster)

• Problem 23

  • Only 62 uneven numbers out of 6965 abundant numbers <= 28123
  • There were no significant performance changes using indexOf or includes() to iterate a large array
  • Took ~4 min to return 26667 abundant number sums from 48.511.255 possible combinations (6965 x 6965)

• Problem 25 (with typescript):

  • Calculating the first Fibonacci Number to have N digits.

  - `$ Number Fib(4782) has 1000 digits or more default: 112.99ms`
  - `$ Number Fib(9567) has 2000 digits or more default: 826.671ms`
  - `$ Number Fib(14352) has 3000 digits or more default: 2.301s`
  - `$ Number Fib(19137) has 4000 digits or more default: 5.464s`
  - `$ Number Fib(23922) has 5000 digits or more default: 11.048s`
  - `$ Number Fib(28707)) has 6000 digits or more default: 17.485s`
  - `$ Number Fib(33492) has 7000 digits or more default: 29.132s`
  - `$ Number Fib(38277) has 8000 digits or more default: 44.357s`
  - `$ Number Fib(43062) has 9000 digits or more default: 59.722s`
  - `$ Number Fib(47847) has 10000 digits or more default: 1:24.364 (m:ss.mmm)`