Project Euler 155 Counting Capacitor Circuits

It was very complicated and hard problem when I saw this problem for the first time.
at that time I thought I could not solve this one.
and actually gave up to solve it. because I can't come up with any idea and Algorithm.

after one year from that time with algorithm study.
I have confidence and retry to solve it.
I got an answer of that problem.

Hint is dynamic problem and bruteforce and hashset

that is all
If you have more detail of it reply plz~


https://projecteuler.net/problem=155

An electric circuit uses exclusively identical capacitors of the same value C.
The capacitors can be connected in series or in parallel to form sub-units, which can then be connected in series or in parallel with other capacitors or other sub-units to form larger sub-units, and so on up to a final circuit.

Using this simple procedure and up to n identical capacitors, we can make circuits having a range of different total capacitances. For example, using up to n=3 capacitors of 60 F each, we can obtain the following 7 distinct total capacitance values:

If we denote by D(n) the number of distinct total capacitance values we can obtain when using up to n equal-valued capacitors and the simple procedure described above, we have: D(1)=1, D(2)=3, D(3)=7 ...

Find D(18).

Reminder : When connecting capacitors C₁, C₂ etc in parallel, the total capacitance is C_T = C₁ + C₂ +...,
whereas when connecting them in series, the overall capacitance is given by: 

Project Euler 200 prime-proof sqube

We shall define a sqube to be a number of the form, p²q³, where p and q are distinct primes.
For example, 200 = 5²2³ or 120072949 = 23²61³.

The first five squbes are 72, 108, 200, 392, and 500.

Interestingly, 200 is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "200" is 1992008.

Find the 200th prime-proof sqube containing the contiguous sub-string "200".

this problem is not hard but for fun~!
hint is generate numbers until 10^13

Project Euler 201 Subsets with a unique sum

For any set A of numbers, let sum(A) be the sum of the elements of A.
Consider the set B = {1,3,6,8,10,11}.
There are 20 subsets of B containing three elements, and their sums are:

sum({1,3,6}) = 10,
sum({1,3,8}) = 12,
sum({1,3,10}) = 14,
sum({1,3,11}) = 15,
sum({1,6,8}) = 15,
sum({1,6,10}) = 17,
sum({1,6,11}) = 18,
sum({1,8,10}) = 19,
sum({1,8,11}) = 20,
sum({1,10,11}) = 22,
sum({3,6,8}) = 17,
sum({3,6,10}) = 19,
sum({3,6,11}) = 20,
sum({3,8,10}) = 21,
sum({3,8,11}) = 22,
sum({3,10,11}) = 24,
sum({6,8,10}) = 24,
sum({6,8,11}) = 25,
sum({6,10,11}) = 27,
sum({8,10,11}) = 29.

Some of these sums occur more than once, others are unique.
For a set A, let U(A,k) be the set of unique sums of k-element subsets of A, in our example we find U(B,3) = {10,12,14,18,21,25,27,29} and sum(U(B,3)) = 156.

Now consider the 100-element set S = {1², 2², ... , 100²}.
S has 100891344545564193334812497256 50-element subsets.

Determine the sum of all integers which are the sum of exactly one of the 50-element subsets of S, i.e. find sum(U(S,50)).

I solved this problem for 2hours coding.
I was'nt able to solve this using brutefoce, so I made algorithm.

Project Euler 401 Sum of squares of divisors

The divisors of 6 are 1,2,3 and 6.
The sum of the squares of these numbers is 1+4+9+36=50.

Let sigma2(n) represent the sum of the squares of the divisors of n. Thus sigma2(6)=50.

Let SIGMA2 represent the summatory function of sigma2, that is SIGMA2(n)=∑sigma2(i) for i=1 to n.
The first 6 values of SIGMA2 are: 1,6,16,37,63 and 113.

Find SIGMA2(10¹⁵) modulo 10⁹.

I have to found SIGMA2(10^15)

for bruteforce I cant't solve in my life time

hint 

1^2 + 2^2 + 3^2 + 4^2+ 5^2 + .... N^2 = n(n+1)(2n+1)/6

and what you can do is find answer.~!!!!!!

Project Euler 110

In the following equation x, y, and n are positive integers.

1 x

+

1 y

=

1 n

It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred.

What is the least value of n for which the number of distinct solutions exceeds four million?

My solution~!

1/x + 1/y = 1/n
n/x + n/y = 1
n + nx/y = x
ny + nx = xy
xy - ny -nx =0
xy -ny -nx + n^2 = n^2
(x-n)(y-n) = n^2

if I change x-n = A
               y-n = B

AB = n^2
A and B is divisor of n^2
so we can calculate count of divisors of n^2.

just find n that divisorCount/2 exceeds four million.

Project Euler 148 Pascal's triangle

I solved this one by looking at pattern. Triangular number fractal??? anyway I just used triangular function. from F(1) to F(7) = n(n+1)/2 F(7^2) = F(7)*F(7) F(7^3) = F(7)*F(7)*F(7) what is if F(7^a-3) ? we know that the power of 7 grater than (7^a)-3 is a so we can find this val v = 7^a/7^(a-1) r = 7^a mod 7^(a-1) and finally got recursive function F(7^a-1) = if (r >0) F(v)*F(7)*F(7) + (v+1) * F(r) else F(v)*F(7)*F(7) and Finally I got answer quickly index : 1 1 index : 2 11 index : 3 111 index : 4 1111 index : 5 11111 index : 6 111111 index : 7 1111111 index : 8 1......1 index : 9 11.....11 index : 10 111....111 index : 11 1111...1111 index : 12 11111..11111 index : 13 111111.111111 index : 14 11111111111111 index : 15 1......1......1 index : 16 11.....11.....11 index : 17 111....111....111 index : 18 1111...1111...1111 index : 19 11111..11111..11111 index : 20 111111.111111.111111 index : 21 111111111111111111111 index : 22 1......1......1......1 index : 23 11.....11.....11.....11 index : 24 111....111....111....111 index : 25 1111...1111...1111...1111 index : 26 11111..11111..11111..11111 index : 27 111111.111111.111111.111111 index : 28 1111111111111111111111111111 index : 29 1......1......1......1......1 index : 30 11.....11.....11.....11.....11 index : 31 111....111....111....111....111 index : 32 1111...1111...1111...1111...1111 index : 33 11111..11111..11111..11111..11111 index : 34 111111.111111.111111.111111.111111 index : 35 11111111111111111111111111111111111 index : 36 1......1......1......1......1......1 index : 37 11.....11.....11.....11.....11.....11 index : 38 111....111....111....111....111....111 index : 39 1111...1111...1111...1111...1111...1111 index : 40 11111..11111..11111..11111..11111..11111 index : 41 111111.111111.111111.111111.111111.111111 index : 42 111111111111111111111111111111111111111111 index : 43 1......1......1......1......1......1......1 index : 44 11.....11.....11.....11.....11.....11.....11 index : 45 111....111....111....111....111....111....111 index : 46 1111...1111...1111...1111...1111...1111...1111 index : 47 11111..11111..11111..11111..11111..11111..11111 index : 48 111111.111111.111111.111111.111111.111111.111111 index : 49 1111111111111111111111111111111111111111111111111 index : 50 1................................................1 index : 51 11...............................................11 index : 52 111..............................................111 index : 53 1111.............................................1111 index : 54 11111............................................11111 index : 55 111111...........................................111111 index : 56 1111111..........................................1111111 index : 57 1......1.........................................1......1 index : 58 11.....11........................................11.....11 index : 59 111....111.......................................111....111 index : 60 1111...1111......................................1111...1111 index : 61 11111..11111.....................................11111..11111 index : 62 111111.111111....................................111111.111111 index : 63 11111111111111...................................11111111111111 index : 64 1......1......1..................................1......1......1 index : 65 11.....11.....11.................................11.....11.....11 index : 66 111....111....111................................111....111....111 index : 67 1111...1111...1111...............................1111...1111...1111 index : 68 11111..11111..11111..............................11111..11111..11111 index : 69 111111.111111.111111.............................111111.111111.111111 index : 70 111111111111111111111............................111111111111111111111

Project Euler 169

I sovled thinking about more than 10hours.

anyway sovled it.

hint
1. binary
2. even number , odd number

Project Euler 277 A Modified Collatz sequence

My answer was
left - right and right - left brute force

any good idea is expand sequence and find x

anyway I success

Project Euler 162 Hexadecimal numbers

This problem I thought about more than 2 hours.

My access was combination~!

and Finally got answer O(n^3)

16length ^ 3

Other people solved it O(n)

Project Euler 387 Harshad Numbers

This is an easy problem.
when we solve problem there are something to be considered.
I will tell you one tip.


1. from small number to Big number
 - problem give us find big number for example sum of over 10^14. just find the answer of smaller number ex) 10^3, 10^4 and check your logic if it is working fine.

I solve this problem by using dp.

Project Euler 500

I thought much time and finally got hint

min heap

Project Euler 501 Eight Divisors

I think much time to solve this problem.

but easily i got depressed

because finding primes under 10^12 is too big.

my computer can only 10^9 by using Prime sieve.

so I had to find how to count primeCount under some number.

finally I solved it~!