Updates from July, 2016 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 7:29 pm on July 4, 2016 Permalink | Reply  

    Problem 50: Consecutive prime sum 

    *Difficulty: Medium

    Problem:

    The prime 41, can be written as the sum of six consecutive primes:

    41 = 2 + 3 + 5 + 7 + 11 + 13

    This is the longest sum of consecutive primes that adds to a prime below one-hundred.

    The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

    Which prime, below one-million, can be written as the sum of the most consecutive primes?

    How to solve:

    1.Brute force

    Create a list of prime numbers which is smaller than 1000000, iterate each prime number p in the list, check all possible consecutive prime numbers than can add up to form the p. If it is, and the consecutive length is bigger than the previous one, then update the maximum consecutive length as well as the prime number holding that length.
    Solution took so damn long, more than 90 seconds.
    There are many ways to create a list of prime numbers, here I was using sieve Eratosthenes. Screen Shot 2016-07-05 at 2.11.32 AM

    Then brute force

    Screen Shot 2016-07-05 at 2.12.38 AM

    2.Using consecutive prime sum property

    Accidentally, I come up with this table

    Screen Shot 2016-07-05 at 2.16.27 AM

    For example, if you want to calculate consecutive sum from 2 to 5,

    we can do it just by take the consecutive sum from 2 of 5 = 10, subtract it from consecutive sum from 2 of 2 = 2, the result is 8, then add 2 to the result, which produces 10.

    Let f(n) is the consecutive prime sum from 2 of a number n , then the consecutive sum from i to j (inclusive) is f(j) – f(i)+i , the consecutive length is j – i +1

    The first step is creating a prime number list, and f(n) of each prime . (We can do as exactly as the brute force method).

    Then apply the formula above, we got

    Screen Shot 2016-07-05 at 2.25.13 AM

    Took  11114 ms

    It’s 2:30 AM, i’m so tired so I cannot write fast code. You can make it better, can’t you? :>

    Advertisements
     
  • loctv 4:45 pm on July 4, 2016 Permalink | Reply
    Tags:   

    Problem 48: Self powers 

    *Difficulty: very easy

    Problem:

    The series, 11 + 22 + 33 + … + 1010 = 10405071317.

    Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.

    How to solve:

    I think this problem is no more than teaching you how to use APIs. This problem is just the matter of picking language, and I think Java is the best suit for this kind of problem – dealing with big numbers.

    Screen Shot 2016-07-04 at 11.42.41 PM

     

     
  • loctv 11:57 am on July 4, 2016 Permalink | Reply
    Tags:   

    Problem 25: 1000-digit Fibonacci number 

    *Difficulty: Easy

    Problem:

    The Fibonacci sequence is defined by the recurrence relation:

    Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

    Hence the first 12 terms will be:

    F1 = 1
    F2 = 1
    F3 = 2
    F4 = 3
    F5 = 5
    F6 = 8
    F7 = 13
    F8 = 21
    F9 = 34
    F10 = 55
    F11 = 89
    F12 = 144

    The 12th term, F12, is the first term to contain three digits.

    What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

    How to solve:

    To deal with a number having thousands digits, my choice is Java.

    Screen Shot 2016-07-04 at 6.56.02 PM

    Solution took 330 ms

     
  • loctv 11:31 am on July 4, 2016 Permalink | Reply  

    Library Management Sofware 

    I wrote it and recored the demo.
    I don’t intend to share the code, because I think it’s dirty and the program has not been completed yet.

     
  • loctv 11:12 am on July 4, 2016 Permalink | Reply
    Tags:   

    Problem 24:Lexicographic permutations 

    *Difficulty: Easy

    Problem:

    A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

    012   021   102   120   201   210

    What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

    How to solve:

    1. Brute force, generate all lexicographic permutations, stop when the number is the 1000000th lexicographic permutation
    2. Analyze

    Here is the second way, I don’t write code for this problem, because I feel tired, and because I think it’s unnecessary.

    A 2-digits number has 2 = 2! lexicographic permutations

    A 3-digits number has 6 = 3! lexicographic permutations

    Hence, n-digits number has n! lexicographic permutations

    Here we have ten digits , range from 0 to 9 to form a 10-digits number (include 0 leading).

    So the total lexicographic permutations of this number would be 10! (or 9!*10) . It means every digit in a n-digits number has (n-1)! lexicographic permutation. (*)

    The 1st lexicographic permutation is 0123456789, the 362881th (9!+1) lexicographic permutation is 1023456789, the 725761th is 2013456789 (9!*2 +1 ) , the 1088641th is 301456789, and so on.

    1000000 is bigger than 725761 but smaller than 1088641 , we sure that the first number will be 2, leave out 013456789.

    n = 1000000 – 725761 = 274239

    s = 2

    From (*), we now that in order to know which number is the first number in the list 013456789, we must divide n = 274239 to (k-1)!, which is (9-1)! = 8!, the result is 6.8, we round it to 6. the 6th number in the list 013456789 (0 is the 0th number), is 7, leave out 01345689

    n = 274239 – 6*8! = 32319

    s = 27

    Like we did above, n = 32319 divide to (k-1)!, which is (8-1)! = 7!, the result is 6.4, but we round it to 6. the 6th number in the list 01345689 is 8, leave out 0134569

    n = 32319 – 6*7! = 2079

    s = 278

    Continue, n = 2079 / 6! = 2.9, round to 2. The 2th number in the list 0134569 is 3, leave out 014569

    n = 2079-2*6! = 639

    s =2783

    Continue, n = 639 / 5!  = 5.3, round to 5. The 5th number in the list 014569 is 9, leave out 01456

    n = 639 – 5*5! = 39

    s = 27839

    Continue, n = 39/4! = 1.6, round to 1, the 1th number in the list 01456 is 1, leave out 0456

    n = 39 – 1*4! = 15

    s = 278391

    Continue, n = 15/3! = 2.5, round to 2, the 2th number in the list 0456 is 5 , leave out 046

    n = 15- 2*3! = 3

    s = 2783915

    Continue, n = 3/2! = 1.5, round to 1, the 1th number in the list 046 is 4, leave out 06

    n = 3 – 1*2! = 1

    s = 27839154

    Continue, n = 1/1! = 1, the 1th number in the list 06 is 6

    n = 1 – 1*1! = 0

    s = 278395146

    the list now has only one number, 0. We just need take 0 and add to the last of s.

    The thing I wrote above is also what the program produces. So I don’t give you the code (which obviously you can write by yourself :> )

    Update: which n bigger than 10!, you have to make it smaller.

    For example we have n=  10.000.000, divide it to 10! = 2.8, round to 2. Then n = n – 2*10!. Now it’s smaller than 10!. It means you can apply the above algorithm.

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel