## Re: [hackers-il] Finding the Graham's Function

Expand Messages
• ... OK, so I ll revamp it. I think I ll dedicate an entire slide to it. ... Actually it s if n + largest_factor is factored to an even power of largest_factor.
Message 1 of 5 , Jul 31, 2003
On Wed, 30 Jul 2003, Beni Cherniavsky wrote:

> Shlomi Fish wrote on 2003-07-30:
>
> > 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.
> >
> 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 --

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

> 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.

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

> 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.
>

OK, I'll fix it.

> - 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 :-).
>

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
> all memory :-(.
>

He heh. Guess it's a bug.

Regards,

Shlomi Fish

>

----------------------------------------------------------------------
Shlomi Fish shlomif@...

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

Falk Fish
• OK, the revamped slides are available here: http://vipe.technion.ac.il/~shlomif/lecture/Perl/Graham-Function/ Regards, Shlomi Fish ... Shlomi Fish
Message 2 of 5 , Jul 31, 2003
OK, the revamped slides are available here:

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

Regards,

Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish shlomif@...

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

Falk Fish
• ... 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
Message 3 of 5 , Aug 8, 2003
On Wed, 30 Jul 2003, Beni Cherniavsky wrote:

> Shlomi Fish wrote on 2003-07-30:
>
> > 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.
> >
> 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 :-).
>

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

Regards,

Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish shlomif@...