Problem 1 Rehash

by

Well Nick mentioned earlier today in the office that he had thought of a quicker way to accomplish the first problem.  I’m not sure if this is what he meant, but what I came up with is roughly this: you don’t need to run past all the multiples of each number (3 and 5 in our case) since you can run over the lcm instead.  There will be a fixed amount added each time you pass a multiple of the lcm.

So for example with the numbers 3 and 5 chosen as the divisors we’re interested in we could organize the multiples into a list as follows:

  • 3 + 5 + 6 + 9 + 10 + 12 +15 = 60
  • 18 + 20 + 21 + 24 + 25 + 27 + 30 = 165
  • 33 + 35 + 36 + 39 + 40 + 42 + 45 = 270
  • . . .

You’ll notice that the difference between each sum here is 105 = 7 * 15 which is the number of divisible numbers below the lcm times the lcm.  Well, you probably get the idea now . . . the only snag is the fudge factor: since 15*66 = 990 we need to pick up the last couple multiples above this guy before we get to 1000 (namely 993,996,999).

It seemed like a good idea to allow as many different dividing factors as you like at the same time, so I rewrote both mine and Nick’s solution to take an arbitrary list of numbers as an argument.  For low values like 1000, the lcm idea doesn’t add much.  But for higher maximum values and more factors, it’s a considerable speedup.

Here are some timing results for 3 and 5:

  • Max = 1000, Lcm = .00083, All = .00081
  • Max = 100000 Lcm = .12, All = .12
  • Max = 10000000 Lcm = 3.1, All = 6.3

Now for 3,5 and 7:

  • Max = 1000, Lcm = .00014, All = .001
  • Max = 100000, Lcm = .012, All = .14
  • Max = 10000000, Lcm = .51, All = 9.5

You can see that the Lcm method actually improves with more factors since we’re skipping ahead faster.  Here’s the (kind of messy) code:

def solution2(divisors = [3,5,7], m_val = max_val):
   nums_lcm = lcm(divisors)

   base_set = set([nums_lcm])

   for j in range(len(divisors)):
     cur_div = divisors[j]
     base_set |= set( cur_div * i for i in range(1, nums_lcm / cur_div) )

   # sum of all numbers below least common multiple
   base_sum = sum(base_set)

   # of summands in the previous example
   num_summands = len(base_set)

   reps = max_val//nums_lcm
   scale = num_summands * nums_lcm

   big_skip = nums_lcm * reps
   fudge_set = set( i + big_skip for i in base_set if i + big_skip < max_val )    fudge = sum(fudge_set)    t = time()    my_set = set( base_sum + (i*scale) for i in xrange(0,reps))    print_answer(sum(my_set) + fudge, time()-t) [/sourcecode] Note that I don't start the clock until after doing the setup calculations since technically this information would be given to us as part of specifying which factors to use. Finally, here is some number magic: the answers for higher maximum values in the case of the factors 3 and 5 are as follows:

  • 1000 => 233168
  • 10000 => 23331668
  • 100000 => 2333316668
  • 1000000 => 233333166668

Holy shit, no?

Tags: ,

3 Responses to “Problem 1 Rehash”

  1. Nick Says:

    That’s an interesting pattern at the end there, I’d not noticed that. Perhaps something similar happens for other choices of divisors?

    Your solution isn’t quite the one I had in mind. I’ll post mine sometime next week.

  2. sumidiot Says:

    Also, do you really want to use max_val inside the function, like on lines 16 and 20 above?

    And your for loop in lines 6-8… couldn’t that be just

    for cur_div in divisors:
        base_set |= ...
    
    • ericfinster Says:

      Yeah, you’re right. I had this global variable sitting around in my source file and I wasn’t too careful about cleaning it up before I posted. And I really need to get used to having the iterators around. I still think in terms of C whenever I’m doing imperative style stuff. Need to break that habit.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s


%d bloggers like this: