One thing I learned early on from the Euler puzzles is that
understanding and applying number theory can transform a seemingly
impossible problem into a fairly trivial computation. I approach each
problem with this belief, but seldom have the experience to make the
transformation myself. I definitely appreciate the insights you have
given here!

Dana DeLouis wrote:
sequential prime factors have a product less than or equal to a given
power of ten to solve Euler 69
... But, I have no idea why this should work

Hi. Glad you find this interesting. :)

Let's find the Totient of a large number ...100000000000000
We really don't want to loop this many times calling the GCD function.
Instead, this function relies on Number Theory.
The real key is to have a program that finds the prime factors of a
number. Just being able to divide by the prime number 2 saves a lot of
time. Powers of 10 factor into 2 and 5. (That's why we can do this by
inspection) Once we have the prime factors, the rest is easy. Here's s
small demo:

Sub Demo()
'// = = = = = = = = = = = = = = = = = = =
'// By: Dana DeLouis
'// The EulerPhi of 100000000000000 (1E14)
'// Factors: 2^14 * 5^14
'// = = = = = = = = = = = = = = = = = = =

Dim n As Double

n = Fx(2, 14) * Fx(5, 14)
Debug.Print FormatNumber(n, 0, , , vbTrue)
End Sub

returns:
40,000,000,000,000

Private Function Fx(n As Double, p As Double) As Double
Fx = (n - 1) * n ^ (p - 1)
End Function


(We note that for a Prime number p, the EulerPhi is just p-1.)
So, for the puzzle n / EulerPhi[n].
We want the numerator as large as possible, and the denominator as small
as possible. So, from number theory above, we want the Prime factors to
be as small as possible.(basically, sequential). We also want the power
of each prime to be as small as possible also, which would be 1. So,
basically, we want 2^1 * 3^1 * 5^1 *...etc

BTW, what language were you demonstrating below?
The best I can manage is solving for N < 20,000 or
so in less than 60 seconds.

The Brute-Force method was in Mathematica... in 7 seconds.

HTH
Dana DeLouis
= = = = = = = = =


smartin wrote:
Thanks Dana -- This is very interesting, and makes sense.

BTW, what language were you demonstrating below?

[I'm going completely off-topic now...]

Even if I extend your method to odd numbers and optimize my
Totient/Phi function to cut the GCD calls in half I see I still have a
O(N^2) solution for Euler 69, which is prohibitive to solve by brute
force over 1 <= N <= 1,000,000. The best I can manage is solving for N
< 20,000 or so in less than 60 seconds.

However (and you hinted at this), I observe that solving problems like
Euler 69 for various limits that are powers of ten produces a
tantalizing pattern of results...

N <= N having Max N / Phi(N) = (? not coincidentally ?)
10 6 2 * 3
100 30 2 * 3 * 5
1000 210 2 * 3 * 5 * 7
10000 2310 2 * 3 * 5 * 7 * 11

So I might jump to the conclusion that all I need to know is the
sequential prime factors have a product less than or equal to a given
power of ten to solve Euler 69, indeed many POT beyond the
requirement. But, I have no idea why this should work, as my knowledge
of number theory is slim at best. But again, it seems likely this is
the discovery I am supposed to make here?



Dana DeLouis wrote:
shall have to repeat my experiments with all the interesting GCD
algorithms.

Hi. In the quest for speed to solve the max ratio problem, consider
looking into your Totient function as well.
If (a,b) are Coprime, is (2*a, b) coprime as well? How about (3*a,b).

Here is your Totient function. (I just modified it a little here)

Public Function Totient(ByVal n As Long) As Long
' Returns Euler's Totient (Phi) function of N such that
' Totient = the number of numbers less than N that are relatively prime
' to N.

Dim i As Long
Dim Result As Long
With WorksheetFunction
Result = 1
For i = 2 To n - 1
Result = Result - (.Gcd(i, n) = 1)
Next i
Totient = Result
End With
End Function

When you have a number like say 50, you scan each number 1 - 49.
Let's look at this same thing in a different order...

Sub Demo()
Dim n
For n = 1 To 25
Debug.Print WorksheetFunction.Gcd(n, 50);
Next n
Debug.Print
For n = 49 To 26 Step -1
Debug.Print WorksheetFunction.Gcd(n, 50);
Next n
End Sub

Returns:
1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25
1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2

Do you notice anything on the Coprimes?

So, with Version #1, we could start with:

Sub ShowIt()
'We could do this...
Debug.Print Totient(1000)
'Or this...
Debug.Print 2 * Totient(500)
End Sub

Returns:
400
400

You get the idea with the other primes as well.

I was at the point of thinking this problem could not be solved
by brute force,

If interested in a brute-force approach in another program...

m = Table[n/EulerPhi[n], {n, 1000000}];

' The Max Value is:

Max[m]
17017/3072

'Or
N[%]
5.539388020833333

'Which comes from the number:

Ordering[m, -1]
{510510}

'Whose reference already mentioned pointed to:

2*3*5*7*11*13*17
510510

= = = = =
HTH :)
Dana DeLouis



smartin wrote:
Many thanks to you and everyone else for all the tips and comments!
I shall have to repeat my experiments with all the interesting GCD
algorithms.

BTW you are only missing one thing in your solution -- Euler #69
asks for the largest ratio N/Totient(N) (^:

Peter T wrote:
I may be guilty of testing code without bothering to figure what it
was I was actually testing!

Sub test()
Dim nn As Long, result As Long
Dim t As Double

t = Timer
nn = 1000000

result = Totient(nn)
t = Timer - t
Debug.Print nn, result, Format(t, "0.00")

End Sub

Public Function Totient(ByVal N As Long) As Long
' Returns Euler's Totient (Phi) function of N such that
' Totient = the number of numbers less than N that are relatively
prime
' to N.
Dim i As Long
Dim result As Long
Dim k As Long
result = 1
i = 2
Do While i < N
k = k + 1
'If gcdRR(i, N) = 1 Then Result = Result + 1
'If GCD3(i, N) = 1 Then result = result + 1
If gcdDL(i, N) = 1 Then result = result + 1
i = i + 1
Loop
Totient = result
'Debug.Print , k
End Function

Function gcdRR(ByVal Num1 As Long, ByVal Num2 As Long) As Long
' Rick Rothstein
Dim Remainder As Long
Do
Remainder = (Num2 Mod Num1)
Num2 = Num1
Num1 = Remainder
Loop While Remainder
gcdRR = Num2
End Function

Function gcdDL(a, b)
' = = = = = = = = = =
'// Greatest Common Divisor
'// By: Dana DeLouis - July 24, 2004
' = = = = = = = = = =
Dim v As Variant
v = Array(a, b)
Do While v(1) < 0
v = Array(v(1), v(0) Mod v(1))
Loop
gcdDL = v(0)
End Function

Public Function GCD3(ByVal a As Long, ByVal b As Long) As Long
' adapted from http://tausiq.wordpress.com/2009/05/
If b = 0 Then
GCD3 = a
Else
GCD3 = GCD3(b, a Mod b)
End If
End Function


All three versions, Rick's, yours and GCD3 end up returning the
same result to the test routine of 400,000 with 1,000,000 passed to
the Totient function

Regards,
Peter T



"Dana DeLouis" wrote in message
...
Using Rick's in the OP's Totient function to solve the OP's "Euler
problem
69" took 2.13 sec to return 400000 (outstanding Rick)
Hi. I may be wrong, but I understand that with your solution of
n = 400,000, the Ratio of n / Phi(n) is the greatest.

Problem:
http://projecteuler.net/index.php?se...problems&id=69

If this is correct, than without doing any math, your solution is
a little peculiar. From Number theory, powers of 10 have special
properties. For example, the Phi number of {10,100,1000...) are
{4, 40, 400}. Phi of {40, 400, 4000} are {16, 160, 1600}, or the
constant 2.5.
So, without math, we know that the ratio of your solution is 2.5
From the problem, we were given that the number 6 has the ratio 3.
Therefore, without math, we know that 400,000 can not be the
correct solution.

= = = = =
HTH :)
Dana DeLouis



Peter T wrote:
Here are my test results in Excel 2003 in a fairly old system
(you'll probably get faster results)

Sub test()
Dim nn As Long, x As Long
Dim t As Double
t = Timer
nn = 10000

x = Totient(nn) ' see OP's earlier post
t = Timer - t
Debug.Print nn, x, t
End Sub

with nn = 10000 the Gcd functions get called 9998 times in the
Totient loop

Calling smartin's GCD2 version1
22.6 sec ' state of the VBE not relevant

Calling smartin's GCD2 version2
13.9 sec ' a worthwhile improvment

Calling ATP's Gcd function with loads of debugs
with a reference to atpvbaen.xls in Tools Ref's
4.3 sec ' with the VBE closed
6.4 sec ' with the VBE open but hidden
9.0 sec ' with the VBE active

Clearly I do not replicate the OP's results. For me the ATP
function is much faster, particularly with the VBE closed.

Following Jim's suggestion I opened the atpvbaen.xla nd commented
all Debug lines (why didn't I ever think of that before - thanks
Jim!)

Calling ATP's Gcd with no debugs
1.0 sec ' WOW - how could MS have shipped it with those debugs!

For curiosity I tried Dana DeLouis's version which I renamed to
gcdDL
0.3 sec ' holy crap !

and Rick's which I renamed gcdRR
0.02 sec ' can't be right, need to double check that
0.02 sec ' the prize goes to Rick !

Using Rick's in the OP's Totient function to solve the OP's
"Euler problem 69" took 2.13 sec to return 400000 (outstanding Rick)

That said, I can think of more interesting ways....

Regards,
Peter T



"smartin" wrote in message
...
For giggles, this optimization of my hand-rolled GCD is 2x
faster compared to my previous version... perhaps 20x or more
faster than ATP's GCD for {a,b} around 1800. Alas, it is still
far too slow to handle Euler #69:

Public Function GCD2(ByVal a As Long, ByVal b As Long) As Long
' greatest common divisor
' as structured, it is advantageous to pass the lower of the two
numbers as a
Dim i As Long
Dim Found As Boolean
i = a + 1
Do Until Found
i = i - 1
'If a / i = a \ i And b / i = b \ i Then Found = True
If a / i = a \ i Then
If b / i = b \ i Then Found = True
End If
Loop
GCD2 = i
End Function