## Equation : φ(x) = 2^n

Find all solutions to the equation

$\phi \, (x) \; = \; 2^{n}$,     for   $0 \; \leq n \; \leq \; 12$

Show that for   $0 \; \leq n \; \leq \; 31$,   the equation   $\phi \, (x) \; = \; 2^{n}$   has   $n+2$   solutions
in integers   $n$

and show for   $31 \; < \; n \; < \; 2^{17}$   the equation has always precisely 32 solutions.

$\phi(x) = 2^0 = 1$   ……   x = 1, 2
$\phi(x) = 2^1 = 2$   ……   x = 3, 4, 6
$\phi(x) = 2^2 = 4$   ……   x = 5, 8, 10, 12
$\phi(x) = 2^3 = 8$   ……   x = 15, 16, 20, 24, 30
$\phi(x) = 2^4 = 16$   …..   x = 17, 32, 34, 40, 48, 60
$\phi(x) = 2^5 = 32$   …..   x = 51, 64, 68, 80, 96, 102, 120
$\phi(x) = 2^6 = 64$   …..   x = 85, 128, 136, 160, 170, 192, 204, 240
$\phi(x) = 2^7 = 128$   ….   x = 255,256,272,320,340,384,408,480,510
$\phi(x) = 2^8 = 256$   ….   x = 257,512,514,544,640,680,768,816,960,1020

$\phi(x) = 2^9 = 512$
x = 771, 1024, 1028, 1088, 1280, 1360, 1536, 1542, 1632, 1920, 2040

$\phi(x) = 2^{10} = 1024$
x = 1285, 2048, 2056, 2176, 2560, 2570, 2720, 3072, 3084, 3264, 3840, 4080

$\phi(x) = 2^{11} = 2048$
x = 3855, 4096, 4112, 4352, 5120, 5140, 5440, 6144, 6168, 6528, 7680, 7710, 8160

math grad - Interest: Number theory
This entry was posted in Number Puzzles and tagged . Bookmark the permalink.

### 2 Responses to Equation : φ(x) = 2^n

1. paul says:

Here are the solutions with 0 = 32, the first number in each section is n, so for n = 0 the solutions are 1 and 2 etc.

0
1
2

1
3
4
6

2
5
8
10
12

3
15
16
20
24
30

4
17
32
34
40
48
60

5
51
64
68
80
96
102
120

6
85
128
136
160
170
192
204
240

7
255
256
272
320
340
384
408
480
510

8
257
512
514
544
640
680
768
816
960
1020

9
771
1024
1028
1088
1280
1360
1536
1542
1632
1920
2040

10
1285
2048
2056
2176
2560
2570
2720
3072
3084
3264
3840
4080

11
3855
4096
4112
4352
5120
5140
5440
6144
6168
6528
7680
7710
8160

12
4369
8192
8224
8704
8738
10240
10280
10880
12288
12336
13056
15360
15420
16320

13
13107
16384
16448
17408
17476
20480
20560
21760
24576
24672
26112
26214
30720
30840
32640

14
21845
32768
32896
34816
34952
40960
41120
43520
43690
49152
49344
52224
52428
61440
61680
65280

15
65535
65536
65792
69632
69904
81920
82240
87040
87380
98304
98688
104448
104856
122880
123360
130560
131070

16
65537
131072
131074
131584
139264
139808
163840
164480
174080
174760
196608
197376
208896
209712
245760
246720
261120
262140

17
196611
262144
262148
263168
278528
279616
327680
328960
348160
349520
393216
393222
394752
417792
419424
491520
493440
522240
524280

18
327685
524288
524296
526336
557056
559232
655360
655370
657920
696320
699040
786432
786444
789504
835584
838848
983040
986880
1044480
1048560

19
983055
1048576
1048592
1052672
1114112
1118464
1310720
1310740
1315840
1392640
1398080
1572864
1572888
1579008
1671168
1677696
1966080
1966110
1973760
2088960
2097120

20
1114129
2097152
2097184
2105344
2228224
2228258
2236928
2621440
2621480
2631680
2785280
2796160
3145728
3145776
3158016
3342336
3355392
3932160
3932220
3947520
4177920
4194240

21
3342387
4194304
4194368
4210688
4456448
4456516
4473856
5242880
5242960
5263360
5570560
5592320
6291456
6291552
6316032
6684672
6684774
6710784
7864320
7864440
7895040
8355840
8388480

22
5570645
8388608
8388736
8421376
8912896
8913032
8947712
10485760
10485920
10526720
11141120
11141290
11184640
12582912
12583104
12632064
13369344
13369548
13421568
15728640
15728880
15790080
16711680
16776960

23
16711935
16777216
16777472
16842752
17825792
17826064
17895424
20971520
20971840
21053440
22282240
22282580
22369280
25165824
25166208
25264128
26738688
26739096
26843136
31457280
31457760
31580160
33423360
33423870
33553920

24
16843009
33554432
33554944
33685504
33686018
35651584
35652128
35790848
41943040
41943680
42106880
44564480
44565160
44738560
50331648
50332416
50528256
53477376
53478192
53686272
62914560
62915520
63160320
66846720
66847740
67107840

25
50529027
67108864
67109888
67371008
67372036
71303168
71304256
71581696
83886080
83887360
84213760
89128960
89130320
89477120
100663296
100664832
101056512
101058054
106954752
106956384
107372544
125829120
125831040
126320640
133693440
133695480
134215680

26
84215045
134217728
134219776
134742016
134744072
142606336
142608512
143163392
167772160
167774720
168427520
168430090
178257920
178260640
178954240
201326592
201329664
202113024
202116108
213909504
213912768
214745088
251658240
251662080
252641280
267386880
267390960
268431360

27
252645135
268435456
268439552
269484032
269488144
285212672
285217024
286326784
335544320
335549440
336855040
336860180
356515840
356521280
357908480
402653184
402659328
404226048
404232216
427819008
427825536
429490176
503316480
503324160
505282560
505290270
534773760
534781920
536862720

28
286331153
536870912
536879104
538968064
538976288
570425344
570434048
572653568
572662306
671088640
671098880
673710080
673720360
713031680
713042560
715816960
805306368
805318656
808452096
808464432
855638016
855651072
858980352
1006632960
1006648320
1010565120
1010580540
1069547520
1069563840
1073725440

29
858993459
1073741824
1073758208
1077936128
1077952576
1140850688
1140868096
1145307136
1145324612
1342177280
1342197760
1347420160
1347440720
1426063360
1426085120
1431633920
1610612736
1610637312
1616904192
1616928864
1711276032
1711302144
1717960704
1717986918
2013265920
2013296640
2021130240
2021161080
2139095040
2139127680
2147450880

30
1431655765
2147483648
2147516416
2155872256
2155905152
2281701376
2281736192
2290614272
2290649224
2684354560
2684395520
2694840320
2694881440
2852126720
2852170240
2863267840
2863311530
3221225472
3221274624
3233808384
3233857728
3422552064
3422604288
3435921408
3435973836
4026531840
4026593280
4042260480
4042322160
4278190080
4278255360
4294901760

31
4294967295
4294967296
4295032832
4311744512
4311810304
4563402752
4563472384
4581228544
4581298448
5368709120
5368791040
5389680640
5389762880
5704253440
5704340480
5726535680
5726623060
6442450944
6442549248
6467616768
6467715456
6845104128
6845208576
6871842816
6871947672
8053063680
8053186560
8084520960
8084644320
8556380160
8556510720
8589803520
8589934590

32
8589934592
8590065664
8623489024
8623620608
9126805504
9126944768
9162457088
9162596896
10737418240
10737582080
10779361280
10779525760
11408506880
11408680960
11453071360
11453246120
12884901888
12885098496
12935233536
12935430912
13690208256
13690417152
13743685632
13743895344
16106127360
16106373120
16169041920
16169288640
17112760320
17113021440
17179607040
17179869180

Paul.

2. benvitalis says:

Correction: It’s   $31 < n < 2^{17}$   rather than (2^20)
The proof is based on the fact that the numbers
$2^{2^n} + 1$   $( 5 \leq n < 17)$   are composite