Reachable numbers

Question 1

Definitions

Euler Phi Function (AKA totient function): a function which takes in a positive number and returns the number of positive numbers less than the given number which are co-prime with given number. It is denoted as φ(n).
Reachable number: if there exists a positive integer x such that φ(x) == n, then n is reachable.

Task

Write a function/program to determine if a given positive integer is reachable.

Input

A positive number, in any reasonable format. One can assume that the number is within the capability of the language. Unary input is accepted.

Output

Two consistent values, one for reachable numbers, and the other for unreachable numbers. The two values can be anything, as long as they are consistent.

Testcases

The reachable numbers bellow 100 are:

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46, 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96

(A002202 on OEIS)

Rules

Standard loopholes apply.

Winning criterion

This is code-golf. Submission with lowest byte-count wins.

References

Question 2

also relevant: oeis.org/A264739

Question 3

I offer a bounty to a one-line Retina answer, where the one line is a plain regex (no backticks).

Question 4

@LeakyNun I'm little confused, so far I understand that phi(n) = count { m : 1 <= m <= n AND (m,n) are coprime }.. is that true?

Question 5

@Khaled.K yes, that is true.

Question 6

Jelly, (削除) 7 (削除ここまで) 6 bytes

2RÆṪe@

Not exactly fast. Returns 1 or 0.

Try it online!

How it works

2RÆṪe@ Main link. Argument: n
2 Square; yield n2.
 R Range; yield [1, ..., n2].
 ÆṪ Compute the totient of each integer in the range.
 e@ Exists swap; test if n occurs in the generated array.

Question 7

How does it work?

Question 8

Brute force. There's a lower bound for the totient function, so it's enough to take a large enough range, map totient, and check for occurrences of the input.

Question 9

Can you prove that the square root is the minimum?

Question 10

The square root is actually not a lower bound, but the square root divided by sqrt(2) is. I'm positive that doubling is not required, but a proof will have to wait until I've gotten some sleep. Too tired right now.

Question 11

@LeakyNun Actually, lemma 3 of this paper proves that the square root is a lower bound unless n = 2k with odd k. Since k and 2k have the same totient, doubling is not required.

Question 12

Mathematica, 28 bytes

EulerPhi@Range[#^2]~FreeQ~#&

Like Dennis's Jelly answer, we compute the φ-values of all the numbers up to the square of the input and see if the input appears therein. Returns False if the input is reachable and True if it's not. Yep, that's confusing. But FreeQ is a byte shorter than MatchQ, and hey, the spec said any two consistent values>:)

Question 13

JavaScript (ES6), (削除) 90 (削除ここまで) 82 bytes

Returns 0 or true.

f=(n,x=n*2)=>x?(p=i=>(c=(a,b)=>a?c(b%a,a):b<2)(i,x)+(i&&p(--i)))(x)==n||f(n,x-1):0

This is based on the assumption that if x exists then x ≤ 2n. If proven false, this should be updated to use x=n*n instead of x=n*2 (same size, much slower).

An edge case is n = 128 which requires to compute φ(255).

Demo

f=(n,x=n*2)=>x?(p=i=>(c=(a,b)=>a?c(b%a,a):b<2)(i,x)+(i&&p(--i)))(x)==n||f(n,x-1):0
for(n = 1; n <= 50; n++) {
 console.log(n, f(n));
}

Question 14

Conveniently the Fermat primes are all consecutive giving rise to consecutive edge cases n=2, n=8, n=128, n=32768 and n=2147483648.

Question 15

Axiom, 56 bytes

f(x:PI):Boolean==member?(x,[eulerPhi(i)for i in 1..2*x])

i don't know if it is right...test code and results

(35) -> [i for i in 1..100|f(i)]
 (35)
 [1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46,
 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 100]

The range 1..(2*x) would be ok until input x=500...

Question 16

Pari/GP, 34 bytes

x->![n|n<-[1..x^2],eulerphi(n)==x]

Returns 0 if reachable, 1 if not.

Try it online!

Question 17

05AB1E, 5 bytes

nLÕså

Explanation:

n Square [implicit] input
 L Range [1 .. a]
 Õ Euler totient
 s Put first input at the top of the stack
 å Is it in the list?

Try it online!

Question 18

05AB1E, (削除) 13 (削除ここまで) 12 bytes

EDIT: Saved a byte because input is reused if the stack doesn't have enough elements.

Outputs 1 if reachable, 0 if not.

Relies on assumption that x ≤ 2n if it exists.

xGNÕQi1,q}}0

Try it online!

How it works

 # implicit input 
x # push input, 2 * input
 G # for N in 1..2*input
 # implicit push input
 N # push N
 Õ # push totient of N
 Q # check if both are equal
 i. # if equal
 1, # print 1
 q # quit program
 } # end if
 } # end for
 0 # push 0 if condition never reached
 # implicit print

Question 19

C, 123 bytes

g(a,b){return!a?b:g(b%a,a);}
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}

Try Online

#include <stdio.h>
// gcd function
g(a,b){return!a?b:g(b%a,a);}
// Euler phi(x) function
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}
// check if m is reachable, phi(x) for x in (m , m^2]
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}
main()
{
 // print all reachable number below 50
 for(int x=1; x<50; x++)
 {
 s(x);
 if(t)
 {
 printf(" %d ~ phi(%d) \n", x, k);
 }
 }
}

Question 20

102 bytes

Question 21

Whispers v2, 63 bytes

> Input
>> 12
>> [2]
>> φ(L)
>> Each 4 3
>> 1∈5
>> Output 6

Try it online!

Works by brute force. We square the input, then generate the range [1, 2, ..., x2]. Next we calculate \$\phi(i)\$ for each \$i\$ in this range. Finally, we check if the original input \$x\$ is in the array of \$\phi(i)\$ values.

Question 22

Stax, 6 bytes

┬$τ▀Ω♀

Run and debug it

I'm not sure why 3 golflangs have an Euler Totient function, but I guess it's convenient for these challenges.

0 for reachable and 1 for non-reachable.

Dennis 212k41 gold badges380 silver badges830 bronze badges · Answer 1 · 2017-04-29 04:58:42Z

6

\$\begingroup\$

Jelly, (削除) 7 (削除ここまで) 6 bytes

2RÆṪe@

Not exactly fast. Returns 1 or 0.

Try it online!

How it works

2RÆṪe@ Main link. Argument: n
2 Square; yield n2.
 R Range; yield [1, ..., n2].
 ÆṪ Compute the totient of each integer in the range.
 e@ Exists swap; test if n occurs in the generated array.

Share

Improve this answer

edited Apr 29, 2017 at 6:20

answered Apr 29, 2017 at 4:58

Dennis's user avatar

Dennis

212k41 gold badges380 silver badges830 bronze badges

\$\endgroup\$

10

\$\begingroup\$ How does it work? \$\endgroup\$

Leaky Nun
– Leaky Nun

2017年04月29日 04:59:48 +00:00
Commented Apr 29, 2017 at 4:59
1

\$\begingroup\$ Brute force. There's a lower bound for the totient function, so it's enough to take a large enough range, map totient, and check for occurrences of the input. \$\endgroup\$

Dennis
– Dennis

2017年04月29日 05:02:03 +00:00
Commented Apr 29, 2017 at 5:02
\$\begingroup\$ Can you prove that the square root is the minimum? \$\endgroup\$

Leaky Nun
– Leaky Nun

2017年04月29日 05:59:42 +00:00
Commented Apr 29, 2017 at 5:59
\$\begingroup\$ The square root is actually not a lower bound, but the square root divided by sqrt(2) is. I'm positive that doubling is not required, but a proof will have to wait until I've gotten some sleep. Too tired right now. \$\endgroup\$

Dennis
– Dennis

2017年04月29日 06:05:11 +00:00
Commented Apr 29, 2017 at 6:05
4

\$\begingroup\$ @LeakyNun Actually, lemma 3 of this paper proves that the square root is a lower bound unless n = 2k with odd k. Since k and 2k have the same totient, doubling is not required. \$\endgroup\$

Dennis
– Dennis

2017年04月29日 06:09:52 +00:00
Commented Apr 29, 2017 at 6:09

| Show 5 more comments

Greg Martin 16.7k4 gold badges23 silver badges73 bronze badges · Answer 2 · 2017-04-29 06:39:00Z

Mathematica, 28 bytes

EulerPhi@Range[#^2]~FreeQ~#&

Like Dennis's Jelly answer, we compute the φ-values of all the numbers up to the square of the input and see if the input appears therein. Returns False if the input is reachable and True if it's not. Yep, that's confusing. But FreeQ is a byte shorter than MatchQ, and hey, the spec said any two consistent values>:)

Arnauld 206k21 gold badges187 silver badges670 bronze badges · Answer 3 · 2017-04-29 11:59:50Z

JavaScript (ES6), (削除) 90 (削除ここまで) 82 bytes

Returns 0 or true.

f=(n,x=n*2)=>x?(p=i=>(c=(a,b)=>a?c(b%a,a):b<2)(i,x)+(i&&p(--i)))(x)==n||f(n,x-1):0

This is based on the assumption that if x exists then x ≤ 2n. If proven false, this should be updated to use x=n*n instead of x=n*2 (same size, much slower).

An edge case is n = 128 which requires to compute φ(255).

Demo

f=(n,x=n*2)=>x?(p=i=>(c=(a,b)=>a?c(b%a,a):b<2)(i,x)+(i&&p(--i)))(x)==n||f(n,x-1):0
for(n = 1; n <= 50; n++) {
 console.log(n, f(n));
}

Conveniently the Fermat primes are all consecutive giving rise to consecutive edge cases n=2, n=8, n=128, n=32768 and n=2147483648.

user58988 · Answer 4 · 2017-04-29 07:09:39Z

Axiom, 56 bytes

f(x:PI):Boolean==member?(x,[eulerPhi(i)for i in 1..2*x])

i don't know if it is right...test code and results

(35) -> [i for i in 1..100|f(i)]
 (35)
 [1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46,
 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 100]

The range 1..(2*x) would be ok until input x=500...

alephalpha 51.9k7 gold badges75 silver badges196 bronze badges · Answer 5 · 2017-05-22 07:01:39Z

1

\$\begingroup\$

Pari/GP, 34 bytes

x->![n|n<-[1..x^2],eulerphi(n)==x]

Returns 0 if reachable, 1 if not.

Try it online!

Share

Improve this answer

answered May 22, 2017 at 7:01

alephalpha's user avatar

alephalpha

51.9k7 gold badges75 silver badges196 bronze badges

\$\endgroup\$

Add a comment |

Okx 16.5k5 gold badges45 silver badges114 bronze badges · Answer 6 · 2017-05-19 08:04:49Z

05AB1E, 5 bytes

nLÕså

Explanation:

n Square [implicit] input
 L Range [1 .. a]
 Õ Euler totient
 s Put first input at the top of the stack
 å Is it in the list?

Try it online!

Neil A. 2,1268 silver badges23 bronze badges · Answer 7 · 2017-05-19 02:16:50Z

05AB1E, (削除) 13 (削除ここまで) 12 bytes

EDIT: Saved a byte because input is reused if the stack doesn't have enough elements.

Outputs 1 if reachable, 0 if not.

Relies on assumption that x ≤ 2n if it exists.

xGNÕQi1,q}}0

Try it online!

How it works

 # implicit input 
x # push input, 2 * input
 G # for N in 1..2*input
 # implicit push input
 N # push N
 Õ # push totient of N
 Q # check if both are equal
 i. # if equal
 1, # print 1
 q # quit program
 } # end if
 } # end for
 0 # push 0 if condition never reached
 # implicit print

Khaled.K 1,49710 silver badges12 bronze badges · Answer 8 · 2017-05-22 16:58:14Z

C, 123 bytes

g(a,b){return!a?b:g(b%a,a);}
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}

Try Online

#include <stdio.h>
// gcd function
g(a,b){return!a?b:g(b%a,a);}
// Euler phi(x) function
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}
// check if m is reachable, phi(x) for x in (m , m^2]
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}
main()
{
 // print all reachable number below 50
 for(int x=1; x<50; x++)
 {
 s(x);
 if(t)
 {
 printf(" %d ~ phi(%d) \n", x, k);
 }
 }
}

\$\begingroup\$ 102 bytes \$\endgroup\$

ceilingcat
– ceilingcat

2019年04月29日 22:18:37 +00:00
Commented Apr 29, 2019 at 22:18

score 0 · Answer 9 · 2020-07-04 22:21:02Z

Whispers v2, 63 bytes

> Input
>> 12
>> [2]
>> φ(L)
>> Each 4 3
>> 1∈5
>> Output 6

Try it online!

Works by brute force. We square the input, then generate the range [1, 2, ..., x2]. Next we calculate \$\phi(i)\$ for each \$i\$ in this range. Finally, we check if the original input \$x\$ is in the array of \$\phi(i)\$ values.

Razetime 27.6k3 gold badges31 silver badges77 bronze badges · Answer 10 · 2020-11-09 14:10:06Z

Stax, 6 bytes

┬$τ▀Ω♀

Run and debug it

I'm not sure why 3 golflangs have an Euler Totient function, but I guess it's convenient for these challenges.

0 for reachable and 1 for non-reachable.

Stack Exchange Network

Reachable numbers

Definitions

Task

Input

Output

Testcases

Rules

Winning criterion

References

10 Answers 10

Jelly, (削除) 7 (削除ここまで) 6 bytes

How it works

Mathematica, 28 bytes

JavaScript (ES6), (削除) 90 (削除ここまで) 82 bytes

Demo

Axiom, 56 bytes

Pari/GP, 34 bytes

05AB1E, 5 bytes

05AB1E, (削除) 13 (削除ここまで) 12 bytes

C, 123 bytes

Whispers v2, 63 bytes

Stax, 6 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Hot Network Questions

Reachable numbers

Definitions

Task

Input

Output

Testcases

Rules

Winning criterion

References

10 Answers 10

Jelly, (削除) 7 (削除ここまで) 6 bytes

How it works

Mathematica, 28 bytes

JavaScript (ES6), (削除) 90 (削除ここまで) 82 bytes

Demo

Axiom, 56 bytes

Pari/GP, 34 bytes

05AB1E, 5 bytes

05AB1E, (削除) 13 (削除ここまで) 12 bytes

C, 123 bytes

Whispers v2, 63 bytes

Stax, 6 bytes

Your Answer

Sign up or log in

Post as a guest

Post as a guest

Related

Hot Network Questions