Krish
Reputation: 1081
How to find 2 to the power of an insanely big number modulo 10^9
I have an excessively big number (1500+) digits and I need to find 2 ** that number modulo 1_000_000_000 so I wrote this python:
n = 1
return_value = 2
while n < To_the_power_of:
return_value *= 2
return_value = return_value % 1_000_000_000
n += 1
This returns the correct value for smaller values, but takes too long for bigger values.
If the number is modulo 10 then you get this pattern which could be used.
2 ** 1 modulo 10 = 2
2 ** 2 modulo 10 = 4
2 ** 3 modulo 10 = 8
2 ** 4 modulo 10 = 6
2 ** 5 modulo 10 = 2
2 ** 6 modulo 10 = 4
2 ** 7 modulo 10 = 8
2 ** 8 modulo 10 = 6
I'm hoping that a similar pattern could be used to answer the original problem.
Upvotes: 1
Views: 276
Answers (3)
RARE Kpop Manifesto
Reputation: 2915
To further expand upon the cyclicality aspect of it :
| 10^ 1 starts cycling at := 2^( 1)
( 2)
| with a powers-of-2 period of
:= 5^( 1-1 ) * ( 5-1 )
:= 4
| 0x 4
| 8# 4
| 10^ 2 starts cycling at := 2^( 2)
( 4)
| with a powers-of-2 period of
:= 5^( 2-1 ) * ( 5-1 )
:= 20
| 0x 14
| 8# 24
| 10^ 3 starts cycling at := 2^( 3)
( 8)
| with a powers-of-2 period of
:= 5^( 3-1 ) * ( 5-1 )
:= 100
| 0x 64
| 8# 144
| 10^ 4 starts cycling at := 2^( 4)
( 16)
| with a powers-of-2 period of
:= 5^( 4-1 ) * ( 5-1 )
:= 500
| 0x 1F4
| 8# 764
| 10^ 5 starts cycling at := 2^( 5)
( 32)
| with a powers-of-2 period of
:= 5^( 5-1 ) * ( 5-1 )
:= 2500
| 0x 9C4
| 8# 4704
| 10^ 6 starts cycling at := 2^( 6)
( 64)
| with a powers-of-2 period of
:= 5^( 6-1 ) * ( 5-1 )
:= 12500
| 0x 30D4
| 8# 30324
| 10^ 7 starts cycling at := 2^( 7)
( 128)
| with a powers-of-2 period of
:= 5^( 7-1 ) * ( 5-1 )
:= 62500
| 0x F424
| 8# 172044
| 10^ 8 starts cycling at := 2^( 8)
( 256)
| with a powers-of-2 period of
:= 5^( 8-1 ) * ( 5-1 )
:= 312500
| 0x 4C4B4
| 8# 1142264
| 10^ 9 starts cycling at := 2^( 9)
( 512)
| with a powers-of-2 period of
:= 5^( 9-1 ) * ( 5-1 )
:= 1562500
| 0x 17D784
| 8# 5753604
| 10^10 starts cycling at := 2^(10)
( 1024)
| with a powers-of-2 period of
:= 5^( 10-1 ) * ( 5-1 )
:= 7812500
| 0x 773594
| 8# 35632624
| 10^11 starts cycling at := 2^(11)
( 2048)
| with a powers-of-2 period of
:= 5^( 11-1 ) * ( 5-1 )
:= 39062500
| 0x 2540BE4
| 8# 225005744
| 10^12 starts cycling at := 2^(12)
( 4096)
| with a powers-of-2 period of
:= 5^( 12-1 ) * ( 5-1 )
:= 195312500
| 0x BA43B74
| 8# 1351035564
| 10^13 starts cycling at := 2^(13)
( 8192)
| with a powers-of-2 period of
:= 5^( 13-1 ) * ( 5-1 )
:= 976562500
| 0x 3A352944
| 8# 7215224504
| 10^14 starts cycling at := 2^(14)
( 16384)
| with a powers-of-2 period of
:= 5^( 14-1 ) * ( 5-1 )
:= 4882812500
| 0x 12309CE54
| 8# 44302347124
| 10^15 starts cycling at := 2^(15)
( 32768)
| with a powers-of-2 period of
:= 5^( 15-1 ) * ( 5-1 )
:= 24414062500
| 0x 5AF3107A4
| 8# 265714203644
| 10^16 starts cycling at := 2^(16)
( 65536)
| with a powers-of-2 period of
:= 5^( 16-1 ) * ( 5-1 )
:= 122070312500
| 0x 1C6BF52634
| 8# 1615375223064
| 10^17 starts cycling at := 2^(17)
( 131072)
| with a powers-of-2 period of
:= 5^( 17-1 ) * ( 5-1 )
:= 610351562500
| 0x 8E1BC9BF04
| 8# 10703362337404
| 10^18 starts cycling at := 2^(18)
( 262144)
| with a powers-of-2 period of
:= 5^( 18-1 ) * ( 5-1 )
:= 3051757812500
| 0x 2C68AF0BB14
| 8# 54321274135424
| 10^19 starts cycling at := 2^(19)
( 524288)
| with a powers-of-2 period of
:= 5^( 19-1 ) * ( 5-1 )
:= 15258789062500
| 0x DE0B6B3A764
| 8# 336026654723544
| 10^20 starts cycling at := 2^(20)
( 1048576)
| with a powers-of-2 period of
:= 5^( 20-1 ) * ( 5-1 )
:= 76293945312500
| 0x 4563918244F4
| 8# 2126162140442364
| 10^21 starts cycling at := 2^(21)
( 2097152)
| with a powers-of-2 period of
:= 5^( 21-1 ) * ( 5-1 )
:= 381469726562500
| 0x 15AF1D78B58C4
| 8# 12657072742654304
| 10^22 starts cycling at := 2^(22)
( 4194304)
| with a powers-of-2 period of
:= 5^( 22-1 ) * ( 5-1 )
:= 1907348632812500
| 0x 6C6B935B8BBD4
| 8# 66153446556135724
| 10^23 starts cycling at := 2^(23)
( 8388608)
| with a powers-of-2 period of
:= 5^( 23-1 ) * ( 5-1 )
:= 9536743164062500
| 0x 21E19E0C9BAB24
| 8# 417031701446725444
| 10^24 starts cycling at := 2^(24)
( 16777216)
| with a powers-of-2 period of
:= 5^( 24-1 ) * ( 5-1 )
:= 47683715820312500
| 0x A968163F0A57B4
| 8# 2513201307702453664
| 10^25 starts cycling at := 2^(25)
( 33554432)
| with a powers-of-2 period of
:= 5^( 25-1 ) * ( 5-1 )
:= 238418579101562500
| 0x 34F086F3B33B684
| 8# 15170206747314733204
| 10^26 starts cycling at := 2^(26)
( 67108864)
| with a powers-of-2 period of
:= 5^( 26-1 ) * ( 5-1 )
:= 1192092895507812500
| 0x 108B2A2C28029094
| 8# 102131242605000510224
| 10^27 starts cycling at := 2^(27)
( 134217728)
| with a powers-of-2 period of
:= 5^( 27-1 ) * ( 5-1 )
:= 5960464477539062500
| 0x 52B7D2DCC80CD2E4
| 8# 512676455631003151344
| 10^28 starts cycling at := 2^(28)
( 268435456)
| with a powers-of-2 period of
:= 5^( 28-1 ) * ( 5-1 )
:= 29802322387695312500
| 0x 19D971E4FE8401E74
| 8# 3166270744775020017164
| 10^29 starts cycling at := 2^(29)
( 536870912)
| with a powers-of-2 period of
:= 5^( 29-1 ) * ( 5-1 )
:= 149011611938476562500
| 0x 813F3978F89409844
| 8# 20117634570761120114104
| 10^30 starts cycling at := 2^(30)
( 1073741824)
| with a powers-of-2 period of
:= 5^( 30-1 ) * ( 5-1 )
:= 745058059692382812500
| 0x 2863C1F5CDAE42F954
| 8# 120617017534665620574524
| 10^31 starts cycling at := 2^(31)
( 2147483648)
| with a powers-of-2 period of
:= 5^( 31-1 ) * ( 5-1 )
:= 3725290298461914062500
| 0x C9F2C9CD04674EDEA4
| 8# 623713116320214723557244
| 10^32 starts cycling at := 2^(32)
( 4294967296)
| with a powers-of-2 period of
:= 5^( 32-1 ) * ( 5-1 )
:= 18626451492309570312500
| 0x 3F1BDF10116048A5934
| 8# 3743367610021300442454464
| 10^33 starts cycling at := 2^(33)
( 8589934592)
| with a powers-of-2 period of
:= 5^( 33-1 ) * ( 5-1 )
:= 93132257461547851562500
| 0x 13B8B5B5056E16B3BE04
| 8# 23561326650126702654737004
| 10^34 starts cycling at := 2^(34)
( 17179869184)
| with a powers-of-2 period of
:= 5^( 34-1 ) * ( 5-1 )
:= 465661287307739257812500
| 0x 629B8C891B267182B614
| 8# 142467062110662316140533024
| 10^35 starts cycling at := 2^(35)
( 34359738368)
| with a powers-of-2 period of
:= 5^( 35-1 ) * ( 5-1 )
:= 2328306436538696289062500
| 0x 1ED09BEAD87C0378D8E64
| 8# 755023372554174006743307144
| 10^36 starts cycling at := 2^(36)
( 68719476736)
| with a powers-of-2 period of
:= 5^( 36-1 ) * ( 5-1 )
:= 11641532182693481445312500
| 0x 9A130B963A6C115C3C7F4
| 8# 4641141345435154042560743764
| 10^37 starts cycling at := 2^(37)
( 137438953472)
| with a powers-of-2 period of
:= 5^( 37-1 ) * ( 5-1 )
:= 58207660913467407226562500
| 0x 3025F39EF241C56CD2E7C4
| 8# 30045747173622034255464563704
| 10^38 starts cycling at := 2^(38)
( 274877906944)
| with a powers-of-2 period of
:= 5^( 38-1 ) * ( 5-1 )
:= 291038304567337036132812500
| 0x F0BDC21ABB48DB201E86D4
| 8# 170275604152732215544007503324
| 10^39 starts cycling at := 2^(39)
( 549755813888)
| with a powers-of-2 period of
:= 5^( 39-1 ) * ( 5-1 )
:= 1455191522836685180664062500
| 0x 4B3B4CA85A86C47A098A224
| 8# 1131664625026503304364046121044
| 10^40 starts cycling at := 2^(40)
( 1099511627776)
| with a powers-of-2 period of
:= 5^( 40-1 ) * ( 5-1 )
:= 7275957614183425903320312500
| 0x 178287F49C4A1D6622FB2AB4
| 8# 5701207751161120726304276625264
| 10^41 starts cycling at := 2^(41)
( 2199023255552)
| with a powers-of-2 period of
:= 5^( 41-1 ) * ( 5-1 )
:= 36379788070917129516601562500
| 0x 758CA7C70D7292FEAEE7D584
| 8# 35306247616065624457725671752604
| 10^42 starts cycling at := 2^(42)
( 4398046511104)
| with a powers-of-2 period of
:= 5^( 42-1 ) * ( 5-1 )
:= 181898940354585647583007812500
| 0x 24BBF46E3433CDEF96A872B94
| 8# 222737506706414746757455241625624
| 10^43 starts cycling at := 2^(43)
( 8796093022208)
| with a powers-of-2 period of
:= 5^( 43-1 ) * ( 5-1 )
:= 909494701772928237915039062500
| 0x B7ABC627050305ADF14A3D9E4
| 8# 1336536142340500602655742450754744
| 10^44 starts cycling at := 2^(44)
( 17592186044416)
| with a powers-of-2 period of
:= 5^( 44-1 ) * ( 5-1 )
:= 4547473508864641189575195312500
| 0x 3965ADEC3190F1C65B67334174
| 8# 7131326754143103616145554714640564
| 10^45 starts cycling at := 2^(45)
( 35184372088832)
| with a powers-of-2 period of
:= 5^( 45-1 ) * ( 5-1 )
:= 22737367544323205947875976562500
| 0x 11EFC659CF7D4B8DFC904004744
| 8# 43677062634757522706774440400043504
| 10^46 starts cycling at := 2^(46)
( 70368744177664)
| with a powers-of-2 period of
:= 5^( 46-1 ) * ( 5-1 )
:= 113686837721616029739379882812500
| 0x 59AEDFC10D7279C5EED14016454
| 8# 263273376020656236342756642400262124
| 10^47 starts cycling at := 2^(47)
( 140737488355328)
| with a powers-of-2 period of
:= 5^( 47-1 ) * ( 5-1 )
:= 568434188608080148696899414062500
| 0x 1C06A5EC5433C60DDAA16406F5A4
| 8# 1600651366124147430156652054401572644
| 10^48 starts cycling at := 2^(48)
( 281474976710656)
| with a powers-of-2 period of
:= 5^( 48-1 ) * ( 5-1 )
:= 2842170943040400743484497070312500
| 0x 8C213D9DA502DE454526F422CC34
| 8# 10604117316645005571052122336410546064
| 10^49 starts cycling at := 2^(49)
( 562949953421312)
| with a powers-of-2 period of
:= 5^( 49-1 ) * ( 5-1 )
:= 14210854715202003717422485351562500
| 0x 2BCA63414390E575A59C2C4ADFD04
| 8# 53624615012071034535322634130453376404
| 10^50 starts cycling at := 2^(50)
( 1125899906842624)
| with a powers-of-2 period of
:= 5^( 50-1 ) * ( 5-1 )
:= 71054273576010018587112426757812500
| 0x DAF3F04651D47B4C3C0CDD765F114
| 8# 332747701062435217323036014672731370424
| 10^51 starts cycling at := 2^(51)
( 2251799813685248)
| with a powers-of-2 period of
:= 5^( 51-1 ) * ( 5-1 )
:= 355271367880050092935562133789062500
| 0x 446C3B15F9926687D2C40534FDB564
| 8# 2106607305374622315037226100246477332544
| 10^52 starts cycling at := 2^(52)
( 4503599627370496)
| with a powers-of-2 period of
:= 5^( 52-1 ) * ( 5-1 )
:= 1776356839400250464677810668945312500
| 0x 1561D276DDFDC00A71DD41A08F48AF4
| 8# 12541644733357734001234356501501075105364
| 10^53 starts cycling at := 2^(53)
( 9007199254740992)
| with a powers-of-2 period of
:= 5^( 53-1 ) * ( 5-1 )
:= 8881784197001252323389053344726562500
| 0x 6AE91C5255F4C03439524822CC6B6C4
| 8# 65351070511257514006416251110105461533304
| 10^54 starts cycling at := 2^(54)
( 18014398509481984)
| with a powers-of-2 period of
:= 5^( 54-1 ) * ( 5-1 )
:= 44408920985006261616945266723632812500
| 0x 2168D8D9BADC7C1051E9B68ADFE191D4
| 8# 413215433156556174040507515550533770310724
| 10^55 starts cycling at := 2^(55)
( 36028797018963968)
| with a powers-of-2 period of
:= 5^( 55-1 ) * ( 5-1 )
:= 222044604925031308084726333618164062500
| 0x A70C3C40A64E6C51999090B65F67D924
| 8# 2470303610051447154243146204413313731754444
| 10^56 starts cycling at := 2^(56)
( 72057594037927936)
| with a powers-of-2 period of
:= 5^( 56-1 ) * ( 5-1 )
:= 1110223024625156540423631668090820312500
| 0x 3433D2D433F881D97FFD2D38FDD073DB4
| 8# 15031722650317704035457777226470773501636664
| 10^57 starts cycling at := 2^(57)
( 144115188075855872)
| with a powers-of-2 period of
:= 5^( 57-1 ) * ( 5-1 )
:= 5551115123125782702118158340454101562500
| 0x 105031E2503DA893F7FF1E21CF51243484
| 8# 101201436112017324223757774361034752111032204
| 10^58 starts cycling at := 2^(58)
( 288230376151711744)
| with a powers-of-2 period of
:= 5^( 58-1 ) * ( 5-1 )
:= 27755575615628913510590791702270507812500
| 0x 5190F96B91344AE3D7FB96A90C95B50694
| 8# 506207626562115045343657756265220622555203224
| 10^59 starts cycling at := 2^(59)
( 576460752303423488)
| with a powers-of-2 period of
:= 5^( 59-1 ) * ( 5-1 )
:= 138777878078144567552953958511352539062500
| 0x 197D4DF19D605767337E9F14D3EEC8920E4
| 8# 3137246761472601273163157647612323735442220344
| 10^60 starts cycling at := 2^(60)
( 1152921504606846976)
| with a powers-of-2 period of
:= 5^( 60-1 ) * ( 5-1 )
:= 693889390390722837764769792556762695312500
| 0x 7F7285B812E1B50401791B6823A9EADA474
| 8# 17734502670045606650100057106664043523653322164
| 10^61 starts cycling at := 2^(61)
( 2305843009213693952)
| with a powers-of-2 period of
:= 5^( 61-1 ) * ( 5-1 )
:= 3469446951953614188823848962783813476562500
| 0x 27D3C9C985E688914075D8908B2519643644
| 8# 117517116230274642110500353542204262243131033104
| 10^62 starts cycling at := 2^(62)
( 4611686018427387904)
| with a powers-of-2 period of
:= 5^( 62-1 ) * ( 5-1 )
:= 17347234759768070944119244813919067382812500
| 0x C722F0EF9D80AAD6424D3AD2B7B97EF50F54
| 8# 616213607371660052553102232353225573457675207524
| 10^63 starts cycling at := 2^(63)
( 9223372036854775808)
| with a powers-of-2 period of
:= 5^( 63-1 ) * ( 5-1 )
:= 86736173798840354720596224069595336914062500
| 0x 3E3AEB4AE1383562F4B82261D969F7AC94CA4
| 8# 3707272645341160325427513404230354551757262246244
| 10^64 starts cycling at := 2^(64)
(18446744073709551616)
| with a powers-of-2 period of
:= 5^( 64-1 ) * ( 5-1 )
:= 433680868994201773602981120347976684570312500
| 0x 13726987666190AEEC798ABE93F11D65EE7F34
| 8# 23344646073146062053566171425372237421654573477464
Upvotes: 0
user58697
Reputation: 7923
Your code makes about 10 ** 1500 iterations, which is indeed insanely long. A useful general technique is exponentiation by squaring, which will give you the result in about 4500 iterations.
If you want to follow the path of the @Prune's answer, you should go along the lines of Fermat's Little Theorem, specifically the Euler's generalization. phi(1_000_000_000) is easy to compute, because 10 ** 9 = (2 ** 9) * (5 ** 9), the product of 2 powers of primes.
Upvotes: 1
Prune
Reputation: 77900
You already know that the sequence will repeat. You found the cycle of 4 for mod 10; now, just find it for a billion:
mod_billion = set()
pow_2 = 2
billion = 10**9
while pow_2 not in mod_billion:
mod_billion.add(pow_2)
pow_2 *= 2
if pow_2 > billion:
pow_2 -= billion
print (pow_2, len(mod_billion))
Three seconds later, we get:
512 1562508
Thus, this sequence repeats every 1562508 items. To find your value for your given power:
cycle = 1562508
small_power = big_power % cycle
result = (2 ** small_power) % billion
Upvotes: 4
Related Questions
- What is the most efficient way to calculate power of larger numbers in python
- Calculating very large power
- Modular exponentiation of large number
- How to calculate 2 to the power of a large number modulo another large number?
- Finding unit digit of large powers
- Find modulo of large number with large number
- Calculating very large exponents in python
- Finding remainder mod involving exponent and division involving huge numbers
- Finding digits in powers of 2 fast
- Python implementing pow() for exponentiation by squaring for very large integers