Subject: Finding the Graham's Function

From: Shlomi Fish <[email-masked]>
Date: Wed, 30 Jul 2003 12:27:57 +0300 (IDT)

Here:

http://vipe.technion.ac.il/~shlomif/lecture/Perl/Graham-Function/

You can find a lecture and Perl code I wrote for finding the Graham
Function. It was done as part of one of Mark Jason Dominus' Perl Quizes of
the Week.

To calculate the Graham Function one needs to find an increasing sequence
of integers starting from the integer in question, so that their product
is a perfect square and the largest number is as small as possible. Then,
the graham function is the largest number.

My solution to the problem uses some Linear Algebra concepts to solve the
problem.

Regards,

	Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/

An apple a day will keep a doctor away. Two apples a day will keep two
doctors away.

	Falk Fish

---

From: Beni Cherniavsky <[email-masked]>
Date: Wed, 30 Jul 2003 22:35:35 +0300 (IDT)

> My solution to the problem uses some Linear Algebra concepts to solve the
Cute!  I've just read some { Graham (this one!), Knuth (the one ;),
Patashnik }'s "Concrete Mathematics" so I can't resist studying such a
problem ;-).  Some notes:

- The `n + largest_factor` optimization is relatively poorly
  explained, especially in the lecture notes -- at least it took me
  lots of time and code studying to understand it, while the rest was
  easy.  The explanation doesn't mentions that you might need `n +
  2*largest_factor` if `n + largest_factor` divides by
  `largest_factor` an even number of times.  It uses a "SqFact"
  notation that doesn't appear anywhere else, confusing because
  "get_squaring_factors()" is used near it.  And most importantly,
  s/fit a square of /fit any square * /; I couldn't make any sense of
  this sentence for a long time.

- A simple experiment (add ``print "optimized";`` and grep -c for it)
  gives a fascinating result: this optimization works with apparently
  constant probability of about 43% over any range of consecutive
  numbers!  Perhaps not constant -- but it decreases very slowly.  I
  probed short ranges up to ~270000:

  1000-2000: 436/1001 = 0.436
  2000-3000: 437/1001 = 0.437
  10000-10100: 44/101 = 0.436
  20000-20100: 42/101 = 0.416
  70000-70100: 39/101 = 0.386
  200000-200020: 7/21 = 0.333
  267800-267820: 6/21 = 0.285

  The last results suggest slow decrease but their precision is low
  (for big numbers I took ranges of only 20 numbers since it takes
  ages to run).  Any explanation?  Where does 0.43 come from?  I bet
  it involves pi or e :-).

P.S. without arguments it executed Graham(0) which nastily exhausted
     all memory :-(.

-- 
Beni Cherniavsky <[email-masked]>

Put a backslash at the evening to continue hacking onto the next day.

---

From: Shlomi Fish <[email-masked]>
Date: Thu, 31 Jul 2003 10:31:44 +0300 (IDT)

On Wed, 30 Jul 2003, Beni Cherniavsky wrote:

>   explained, especially in the lecture notes --

OK, so I'll revamp it. I think I'll dedicate an entire slide to it.

> at least it took me
>   `largest_factor` an even number of times.

Actually it's if n + largest_factor is factored to an even power of
largest_factor.

> It uses a "SqFact"

OK, I'll fix it.

>   probed short ranges up to ~270000:

You can easily implement a function that runs only this optimization and
fails otherwise. That way it will take much less time, and you can run it
on longer ranges.

> P.S. without arguments it executed Graham(0) which nastily exhausted

He heh. Guess it's a bug.

Regards,

	Shlomi Fish

	Falk Fish

---

From: Shlomi Fish <[email-masked]>
Date: Thu, 31 Jul 2003 10:50:07 +0300 (IDT)

OK, the revamped slides are available here:

Regards,

	Shlomi Fish

	Falk Fish

---

From: Shlomi Fish <[email-masked]>
Date: Fri, 8 Aug 2003 18:58:49 +0300 (IDT)

>   probed short ranges up to ~270000:

Here are my experminet results (don't calculate the entire function -
just checks if the optimization works or not):

1000-2000 : 436
2000-3000 : 437
10000-11000 : 437
20000-21000 : 428
70000-71000 : 439
200000-201000 : 398
267800-268800 : 400

What that means - I don't know. It seems that after 200,000 the ratio has
decreased to about 0.4 instead of 0.43.

Regards,

	Shlomi Fish

	Falk Fish