Project Euler 155 - Counting Capacitor Circuits
Official link: https://projecteuler.net/problem=155
Note: My code takes ~550 seconds to run, but I'm happy with my solution method.
Thought Process
This was quite an easy problem.
All you have to realise is that to find the number of configurations with n capacitors, you can think of it as adding x and n - x capacitors in series and in parallel. This means than you just slowly calculate for each n and use previous calculations, I keep track of the set of capacitances n capacitors can form.Â
Also note that the value 60 is arbitrary, you can choose 1 just as well!
In order to overcome the precision problems from repeated divisions in the series connection case I ended up using the fractions module.
The answer can also be found in this OEIS sequence, but what fun is that!!
Interactive Code
Input an integer (yourinput)
Code will output D(yourinput)