Thursday, June 30, 2016

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 C1, C2 etc in parallel, the total capacitance is CT = C1 + C2 +...,
whereas when connecting them in series, the overall capacitance is given by: 

Wednesday, June 29, 2016

Project Euler 200 prime-proof sqube

We shall define a sqube to be a number of the form, p2q3, where p and q are distinct primes.
For example, 200 = 5223 or 120072949 = 232613.
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

Tuesday, June 28, 2016

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 = {12, 22, ... , 1002}.
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.

Tuesday, June 21, 2016

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(1015) modulo 109.


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.~!!!!!!

Thursday, June 16, 2016

Project Euler 110

In the following equation xy, 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.






Wednesday, June 15, 2016

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

Tuesday, June 14, 2016

Project Euler 169

I sovled thinking about more than 10hours.

anyway sovled it.

hint
1. binary
2. even number , odd number

Monday, June 13, 2016

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

Sunday, June 12, 2016

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)

Tuesday, June 7, 2016

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

Thursday, June 2, 2016

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~!