Problem 070

[Francky]

For limit=10^7, I got it after 19ms of nature* Python.
Obviously I don't presuppose any bound. Interested ?
(* no compilation, no psyco, nothing, basicaly interpreted)
For limit=10^13, 66ms (+1s for pr..), ans=9997908420679

[jfren484]

I didn't see any posts here or in the problem solution forum with a response to several statements that the answer should be n = 1. The reason I disagree with that is because 1 is not a permutation of 1. Just as 123 is not a permutation of 123 - 123 IS 123. The term permutation implies reordering somehow, and the order of digits in 1 or 123 in my example did not change, therefore any number is not a permutation of itself.

[thundre]

I didn't see any posts here or in the problem solution forum with a response to several statements that the answer should be n = 1. The reason I disagree with that is because 1 is not a permutation of 1. Just as 123 is not a permutation of 123 - 123 IS 123. The term permutation implies reordering somehow, and the order of digits in 1 or 123 in my example did not change, therefore any number is not a permutation of itself.

The identity permutation is still a permutation, I think. Otherwise the number of permutations of 4 distinct digits would be 4!-1.

The reason n=1 is incorrect is that the problem statement specifies 1 < n < 10⁷.

[skoczian]

"Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum." How about values of n with repeated digits, would they be regarded as correct solutions? According to Wikipedia those are multiset permutations. I've searched some other problem clarification threads and found problems where multiset permutations are clearly allowed, but I don't find any general statement and the example has no repeated digits.

[sjhillier]

"How about values of n with repeated digits, would they be regarded as correct solutions?

Yes, they are allowed. Just because they can be regarded as 'multiset permutations' doesn't mean they aren't also permutations.

[pri_gua]

Could we change the definition of totient given in this problem definition? This problem defined phi(1) == 1, while for the standard or most widely used definition of phi, we have phi(1) == 0.

NOTE: phi(n) is usually defined to be the number of numbers in range [1, n - 1] that are co-prime to n, in this problem we redefined phi(n) to be the number of numbers in range [1, n] that are co-prime to n. This is not the standard definition, and might create an off-by-one error in the solution to problem 072, if we use a totient sieve. Since, phi(1) shows up as 1, instead of 0.

[jaap]

Could we change the definition of totient given in this problem definition? This problem defined phi(1) == 1, while for the standard or most widely used definition of phi, we have phi(1) == 0.

NOTE: phi(n) is usually defined to be the number of numbers in range [1, n - 1] that are co-prime to n, in this problem we redefined phi(n) to be the number of numbers in range [1, n] that are co-prime to n. This is not the standard definition, and might create an off-by-one error in the solution to problem 072, if we use a totient sieve. Since, phi(1) shows up as 1, instead of 0.

Actually phi(n) really is usually defined to be the number of numbers in range [1, n] that are co-prime to n. That n itself is included in the range makes no difference in most cases since n is not coprime to n when n>1, but it does make a difference when n=1, since 1 is coprime to 1.

This seems arbitrary, but there is a very good reason that we want phi(1)=1. We want phi to be a multiplicative function, i.e. phi(mn)=phi(m)phi(n) when gcd(m,n)=1. Setting m=1 shows that we must have phi(1)=1 to make this work. You could also define phi(n) in terms of the prime factorisation of n, and in that case phi(1) would be the empty product, which is 1 and not 0.

[pri_gua]

It seems like the standard definition of phi(n) is: For n >= 1, let phi(n) denote the number of positive integers not exceeding n that are relatively prime to n. (Elementary Number Theory, 7th Edition, David Burton).

Then, we should change the definition of phi in Problem 69 (View Problem)
I was going for a solution like this to Problem 72:

Code: Select all

Python 3.9.16 (feeb267ead3e6771d3f2f49b83e1894839f64fb7, Dec 29 2022, 14:23:21)
[PyPy 7.3.11 with GCC 10.2.1 20210130 (Red Hat 10.2.1-11)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>> import util as U
>>>> a = 1000000
>>>> b = U.totientSieve(a)
>>>> c = SomeFunction(b) #### This would have been enough if phi(1) == 0.
>>>> YetAnotherFunction(c, SomeOtherFunction(b[0],  b[1])) #### Now, we have to make this adjustment.

[hk]

The text of Problem 69 (View Problem) reads now:

Euler's Totient Function $\phi(n)$ [sometimes called the phi function], is defined as the number of positive integers not exceeding $n$ which are relatively prime to $n$. etc..

I hope this satisfies you.

[pri_gua]

Thanks very much for standardizing the definition of the totient function.

[shaiephraim]

I think n=2 is a valid correct answer(phi(n)=2, they are permutation of each other so the ratio is 1), which is not what the author probably meant, please fix

[SAG145]

I think n=2 is a valid correct answer(phi(n)=2,

Phi(2) = 1, since 1 is the only number less than 2 which is coprime to 2.

[skoczian]

I think n=2 is a valid correct answer(phi(n)=2, they are permutation of each other so the ratio is 1), which is not what the author probably meant, please fix

Sorry to be rather late, but did you look at the post by jaap, four entries above yours?

[shaiephraim]

I think n=2 is a valid correct answer(phi(n)=2, they are permutation of each other so the ratio is 1), which is not what the author probably meant, please fix

Sorry to be rather late, but did you look at the post by jaap, four entries above yours?

No, I opened a new thread(newbie) and the admin merged it