My Weblog

Blog about programming and math

Project Euler 234

Today I solved problem 234. I found more elegant solution for this problem.

For an integer n ≥ 4, we define the lower prime square root of n, denoted by lps(n), as the largest prime ≤ √n and the upper prime square root of n, ups(n), as the smallest prime ≥ √n.

So, for example, lps(4) = 2 = ups(4), lps(1000) = 31, ups(1000) = 37.
Let us call an integer n ≥ 4 semidivisible, if one of lps(n) and ups(n) divides n, but not both.

The sum of the semidivisible numbers not exceeding 15 is 30, the numbers are 8, 10 and 12.
15 is not semidivisible because it is a multiple of both lps(15) = 3 and ups(15) = 5.
As a further example, the sum of the 92 semidivisible numbers up to 1000 is 34825.

What is the sum of all semidivisible numbers not exceeding 999966663333 ?

The problem requires O(n^0.5) order solution. You have to compute prime numbers less than 10^6. Now start computing how many numbers between 4—9,9—25,25—49 …etc are semi divisible but remember some you will count 6 two time between 4–9 , 15 between 9–25 and 35 between 25—49.This is the simple pattern which makes the problem very nice :).

Solved 104 problem in project euler. Now I am immortal in the rank list :).
P.S. Today our 3 friends selected for AmbujX softwares. All the best to them and now they are no more in our league ….Congrats 🙂

Advertisements

March 1, 2009 - Posted by | Programming

11 Comments »

  1. I tried the same approach as you discuss above, but I can’t seem to get the right answer. I get the right answer for 1000, and also the right answer for 1,000,000 (at least as far as I can verify using a slower algorithm that looks at every number), but I can’t get the right answer for 999966663333. My results show that there are 3764437 semi-divisible numbers <= the upper limit and their sum is 1259187438574718464. Am I close? Off by a little? Off by a lot? Would you care to share the correct solution? I am really frustrated…

    Comment by Rothladoad | April 3, 2009 | Reply

  2. you are quite close to answer. Your answer’s last 6 digit 718464 is not matching.you can mail me if you want to know the answer 🙂

    Comment by mukeshiiitm | April 8, 2009 | Reply

  3. hey, I seem to be having the same problem. I seem to be getting a consistent wrong answer of 1259187438573299120

    Comment by Kevin | June 1, 2009 | Reply

  4. hi, I seem to be having the same problem. I seem to be getting a consistent wrong answer of 1259187438574810400.

    Comment by Max | June 5, 2009 | Reply

    • Ya you are quite close to the answer. Only your last six digit does not match with correct answer. As i already explained my method. If you need any other explicit help, please let me know.

      Comment by mukeshiiitm | June 6, 2009 | Reply

  5. Hi

    I dont quite understand the method u explained. Can u elaborate it please…

    Comment by Mahendra | July 16, 2009 | Reply

    • Hi I think i explained the method quite clearly. Can you tell me which part you did not understand.

      Comment by mukeshiiitm | July 16, 2009 | Reply

      • First of all I dont understand why we have to compute prime numbers less than 10^6.

        Secondly, u say “some you will count 6 two time between 4–9 , 15 between 9–25”. How can one count 6 two times?

        To be frank, I am unable to understand what you are trying to explain.

        Comment by Mahendra | July 16, 2009

  6. Check your mail. It is not good to spoil the fun of problem solving 🙂

    Comment by mukeshiiitm | July 16, 2009 | Reply

  7. Hi My solution is similar to yours.
    but answer is 1209808147844016471
    Can you tell me where i am going wrong?
    for i in range(len(p)):
    t1=p[i]
    t2=p[i+1]
    for j in range(t1**2+t1,t2**2,t1):
    if j>999966663333:
    continue
    if (j%t1==0 and j%t2>0):
    pr.append(j)
    for j in range(t2**2-t2,t1**2,-t2):
    if j>999966663333:
    continue
    if (j%t2==0 and j%t1>0):
    pr.append(j)

    here p is my set of primes 2 to 1000003.
    and pr is my set of semi devisible numbers.
    Answer is correct for first 1000 but wrong for the big number 😦
    you can mail me @ shanecruise [at] gmail [dot] com

    Comment by Shashank | May 18, 2010 | Reply

  8. this indentation is messed up. tell me your id. I will mail it.

    Comment by Shashank | May 18, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: