Project Euler 155 - Counting Capacitor Circuits
Official link: https://projecteuler.net/problem=155
Note: My code takes ~550 seconds to run ~76 with pypy, but I'm happy with my solution method.
Official link: https://projecteuler.net/problem=155
Note: My code takes ~550 seconds to run ~76 with pypy, but I'm happy with my solution method.
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!!
Input an integer (yourinput)
Code will output D(yourinput)