PDA

View Full Version : Perl pragram to find φ(n)

shingalated
November 12th, 2007, 12:27 AM
I need a perl program to make a table of n in the first column and φ(n) in the second column. (Phi = the number of relative primes to n)
This is all I have so far... I don't know how to make it a loop or how to write the part that finds what φ(n) is.

#!/bin/perl
#Program to make table of φ(n)
\$n=0;
\$num2 = \$num1+1;
\$num1 = \$num2;

\$n = \$n +1;
\$n = \$num2;
%table = ("n", \$n, "phi (n)", \$num2);

flibitboat
November 12th, 2007, 01:14 AM
oh yes, i have seen this type of problme before and it is one of the most complicated i have ever seen before. it looks like you are **** out of luck because there is no possible way to do it so get over youself and blow a chipmunk.

shingalated
November 12th, 2007, 01:16 AM
oh yes, i have seen this type of problme before and it is one of the most complicated i have ever seen before. it looks like you are **** out of luck because there is no possible way to do it so get over youself and blow a chipmunk.

Oh, that was wonderful...Thanks for your help.

slavik
November 12th, 2007, 01:32 AM
start with writing a program that finds the relative prives when given n ...

Lux Perpetua
November 12th, 2007, 01:39 AM
oh yes, i have seen this type of problme before and it is one of the most complicated i have ever seen before. it looks like you are **** out of luck because there is no possible way to do it so get over youself and blow a chipmunk.Thank you for your completely unhelpful post.

@shingalated - Hint: two numbers are relatively prime when their GCD (greatest common divisor) is 1. So it might help to write a function that finds the GCD of two numbers.

(If speed is an issue, then there are more efficient ways to approach this, such as using the fact that if m and n are relatively prime, then phi(m)*phi(n) = phi(m*n).)

shingalated
November 12th, 2007, 01:43 AM
How do I turn the:

\$n = \$n +1;
\$n = \$num2;
%table = ("n", \$n, "phi (n)", \$num2);

part into a loop so than n increases by one each time?

evymetal
November 12th, 2007, 02:50 AM
#!/bin/perl
#Program to make table of φ(n)
\$n=0;
\$num2 = \$num1+1;
\$num1 = \$num2;

\$n = \$n +1;
\$n = \$num2;
%table = ("n", \$n, "phi (n)", \$num2);

Try:

#!/bin/perl
#Program to make table of φ(n)
\$n=0;
\$maxn = 100;
while (\$n<=\$maxn){
# function will go here.
\$n = \$n +1;
}

I'm not sure what you are doing within the loop though...
You'll also have to look up associative arrays, I'm not sure why you are saving each row to an array.

smartbei
November 12th, 2007, 08:13 AM
Posting about Project Euler questions in a public forum... tsk tsk :p.

You may want to learn more about perl (or rather, any programming language) in a more general way. Perhaps I am wrong but I get the sense that you are just starting to program and I suggest that you start from an earlier Project Euler problem or from general tutorials.

@flibitboat: This is definately possible, as I have solved it :).

Npl
November 12th, 2007, 08:28 AM
the hard part is doing a prime-factorization on n - if you mean finding a fast algorithm for big n, cause noone found one yet.
once you have your prime-factorization its simple. if n = p^k (where p is prime), then phi(n) = p^(k-1) * (p-1). once you got the phi-values for all different prime(-powers) you merely multiplicate them

eg.
n = 177 = 13 * 3^2
phi(13^1) = 1*12 = 12
phi(3^2) = 3*2 = 6
phi(177) = phi(13)*phi(9) = 12*6 = 72

how you do it in perl is your problem :-\"

slavik
November 12th, 2007, 09:10 AM
there is a way to find the GCD of two numbers in a non-brute force way ;)

shingalated
November 13th, 2007, 12:00 AM
Thank you. I think I can figure it out from here.