3
$\begingroup$

I was doing problem 6.3 from here.

To make this less programming and more math oriented: GCDMany is equivalent to using Euclid's method (using mods and NOT subtraction) on an arbitrary number of elements. The problem essentially wants me to calculate how many times I have to recursively call GCDMany given numbers that are $n$ bits long (i.e. 3 (11) is 2 bits long, 1 (1) is 1 bit long 0 (0) is 1 bit long and so on).

The GCDMany upper bound ultimately given was $2n$ as you can see in the answer. I believe I came up with a tighter upper bound.

I did a bit of experimenting with this program I made to test values:

from itertools import combinations
for i in range(1, 25+1): #1 to 200 bits
    j = range(i)
    best = 0
    for c in combs:
        count = gcd_many(list(c))[1] if count > best:
    best = count
print best

First off, I realized after experimenting the worst case scenario always seemed to be when GCDMany was passed only two numbers, making my testing essentially concerned with only the standard GCD function. My logic was: Given there is a longest recursive call, any addition of numbers would result in a path less than or equal to the current path, hence 2 numbers would be the worse case.

My program came up with the following: 1, 3, 4, 6, 7 ... Using OEIS.org I found a series of closed forms for it. Most notably this one seemed legit:

$$a(n) = \frac{6n - 1 + (-1)^n}{4}$$

Can anyone confirm or deny my upper bound, and possibly help me figure out what I can do to prove my conjecture if it is correct?

$\endgroup$
  • $\begingroup$ I don't quite understand. Can you state concisely exactly what property it is that you think the sequence 1,3,4,6,7,... has? $\endgroup$ – Nate Eldredge Apr 22 '14 at 5:20
  • $\begingroup$ Also, you talk about GCDmany being given a number that is less than $n$ bits; but I thought it was supposed to take as input several numbers? $\endgroup$ – Nate Eldredge Apr 22 '14 at 5:23
  • $\begingroup$ @NateEldredge: All my stuff is from experimentation as I can't think of anyway to prove this with my knowledge of discrete math. Honestly, the reason why I choose that particular $a(n)$ is relatively arbitrary, simply because it was the simplest closed form that matched up with my experimentation. $\endgroup$ – Dair Apr 22 '14 at 5:56
  • $\begingroup$ @NateEldredge: Edited question to reflect it is multiple numbers, that was a typo. $\endgroup$ – Dair Apr 22 '14 at 5:57
  • $\begingroup$ @NateEldredge: Also, I am not looking for an answer necessarily, just guidance on what to do to confirm or deny this conjecture, and if it is false, advice as what to look into to come up with a correct solution, as I believe I can find a better upper bound than the solution given. $\endgroup$ – Dair Apr 22 '14 at 5:58
2
+50
$\begingroup$

(Essentially answered in the comments, but just so that we have an answer,)

Lamé's Theorem gives a bound on the number of rounds it takes for Euclid's algorithm to find the gcd of 2 numbers. Statement of the theorem abound on the web, and in introductory Number Theory textbooks.

$\endgroup$
  • $\begingroup$ Will give the bounty when I can... $\endgroup$ – Dair Apr 23 '14 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.