problem 304 Primonacci

거의 3년만에 올일러 문제가 풀렸다 ㅠ 드뎌 200문제를 풀었고 level은 8로 올랐다.

이 문제도 4일걸려서 풀었는데 계속 풀어야할지 의문이긴하다 .ㅎ

It took 4 days to solve this problem. 

finally I solved 200 problems in proejct euler ^^ 

https://projecteuler.net/problem=304

hint : 

 remainder

 x mod a + x mod b ==x mod a + b

이번주 문제 https://projecteuler.net/problem=425 프라임 숫자와, 관련해서 공부해보자

이번주 문제 https://projecteuler.net/problem=425 프라임 숫자와, 관련해서 공부해보자

Project Euler 160 Factorial trailing digits

It took about 8days from start to solving this problem (last non-zero digits of factorial)
First time I searched 0 to 1000000000000.
I doubt that my computer compute this logig in my life?
and searching how to find last zeros count of N factorial

finally I made condition

ex) 10! = 1 * 2* 3* 4 * 5* 6* 7 * 8 *9 *10

2*5 make 0 digit

so we should find multiple of 5
5, 10 that is all

5 = 5*1
10 = 5*2

10! = 5^2 * 2! * (10a +1) (10a +2)  (10a +3) (10a +4) (10a +6).. (10a +9) mod m
10! = 10^2 * 2! * (10a +1) (5a+1) (10a+3) (5a+2) (10a+6 )... (10a+9)..

what if 100! and m is 10 ???

100! = 10^20 * 20! *  ((10a +1) (5a+1) (10a+3) (5a+2) (10a+6 )... (10a+9))^10

so we can use this and solve 1000000000000 ! mod 100000






https://projecteuler.net/problem=160

For any N, let f(N) be the last five digits before the trailing zeroes in N!.
For example,

9! = 362880 so f(9)=36288
10! = 3628800 so f(10)=36288
20! = 2432902008176640000 so f(20)=17664

Find f(1,000,000,000,000)

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

problem 287 in project euler

I took 5 hours to solve this problem. thinking time and coding time is 5hours 1.my first approch this problem was math approach D1, D2, D3, D4 and there is nothing related to math. 2. second was finding pattern. with eclipse tool I was able to draw D1, to D7 but nothing found without only one thing that is black circle. 3. thought lots time and look deeply more and more. 4. finally found that It could be possible that whether all blocks are colorerd black or not if I check only four couners. 5. divide and conquer bruteforce check. 6. I got answer after 5min process. I think it it too long. 7. I started customized removing duplicated conditions. 8. 10second. 9. I changed Math.pow to a * a . 10 finally I can solve this one within 1 second

problem 243

hint is EulerPhi / n-1

and second focus is how to short running time~!

Project Euler problem 303

My effort to solve it

1. make 3digit generator and divide with n

2. 9999 is never solved in time.

3. find 9, 99, 999, 9999 in pattern.

4. finally solve it in 9s

problem 293

This problem was some how easy.

Using DFS and Set

I could solve it.

Problem 491

Examples:

Is the number 2547039 divisible by 11?

First find the difference between sum of its digits at odd and even places.

(Sum of digits at odd places) - (Sum of digits at even places)

= (9 + 0 + 4 + 2) - (3 + 7 + 5)

= 15 - 15 = 0

The number is 0, so the number 2547039 is divisible by 11

I approach this problem by using above condition.

1. recursive function

2. combination

my java code is below

package numberFrom400;

import java.util.Arrays;

import euler.util.EulerUtil;

public class number491 {
 
 public static long totalCase = 0;
 
 public static int total = 0;
 
 public static int sum = 90;
 
 public static void main(String args[]){
  
  long start = System.currentTimeMillis();
  int numbers[] = new int[10];
  searching(0, 0, numbers);
  
  System.out.println(totalCase);
  System.out.println(System.currentTimeMillis()-start);
 }
 
 
 public static void searching(int position, int count, int[]arr ){
  if(position>=arr.length){
   if(count == 10){
    // 여기서 시작한다. 왼쪽 섬
    int subsum = 0;
    for (int i = 0; i < arr.length; i++) {
     if(arr[i] != 0){
      int val = i *arr[i];
      subsum += val;
     }
    }
    
    if((subsum -(sum - subsum))%11 ==0){
//     System.out.println("this num is divisible");
//     System.out.println(Arrays.toString(arr));
//     System.out.println(Arrays.toString(reversse(arr)) + " re ");
     // 여기가 Divisible이 가능한 위치
     
     int twocount = 0;
     for (int i = 0; i < arr.length; i++) {
      if(arr[i]== 2){
       twocount ++;
      }
     }
     
     long leftCase = EulerUtil.getFactorial(10)/(long)Math.pow(2, twocount);
     if(arr[0] ==1  ){
      leftCase = (leftCase - EulerUtil.getFactorial(9)/(long)Math.pow(2, twocount));
     }else if (arr[0] ==2) {
      leftCase = (leftCase - EulerUtil.getFactorial(9)/(long)Math.pow(2, twocount-1));
     }
     
     int[] reverse = reversse(arr);
     
     // right case
     twocount = 0;
     for (int i = 0; i < reverse.length; i++) {
      if(reverse[i]== 2){
       twocount ++;
      }
     }
     
     long rightCase = EulerUtil.getFactorial(10)/(long)Math.pow(2, twocount);
     
     totalCase = totalCase + (leftCase * rightCase );
    }else{
    }
    
    total++;
    return;
   }else if(count > 5){
    return;
   }
   return; 
  }
  
  for (int i = 0; i < 3; i++) {
   
   arr[position] = i;
   searching(position+1, count+i, arr);
   arr[position] = 0;
  }
 }
 
 
 public static int[] reversse (int arr[]){
  int reverse[]= new int[arr.length];
  for (int i = 0; i < arr.length; i++) {
   reverse[i] = 2 - arr[i];
  }
  return reverse;
 }
 
}