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

 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Advertisements

About benvitalis

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s