Can you find a 76-digit multiple of 2⁷⁶, written exclusively with 7s and 6s?

The first 10 multiples of 2^76 are
1       75557863725914323419136
2       151115727451828646838272
3       226673591177742970257408
4       302231454903657293676544
5       377789318629571617095680
6       453347182355485940514816
7       528905046081400263933952
8       604462909807314587353088
9       680020773533228910772224
10      755578637259143234191360

with 2^76 itself being a 23-digit number.

To produce a 76-digit number, 2^76 must be multiplied by a 53- or 54-digit number (between 13,234,889,800,848,442,797,942,539,073,119,405,657,052,993,774,414,062 and 132,348,898,008,484,427,979,425,390,731,194,056,570,529,937,744,140,625).

The last digit can't be a 7, so it must be a 6.

In order for the 76-digit number to start with only 6s and 7s, the multiple of 2^76 must start between 87... and 89... or between 100... and 102..., with the ellipses representing another 51 digits.  This is based on the following table of multiples of 2^76, and allows for carries from lower order digits:

86      6497976280428631814045696
87      6573534144154546137464832
88      6649092007880460460883968
89      6724649871606374784303104
90      6800207735332289107722240
91      6875765599058203431141376
92      6951323462784117754560512
93      7026881326510032077979648
94      7102439190235946401398784
95      7177997053961860724817920
96      7253554917687775048237056
97      7329112781413689371656192
98      7404670645139603695075328
99      7480228508865518018494464
100     7555786372591432341913600
101     7631344236317346665332736
102     7706902100043260988751872
103     7782459963769175312171008

Now where to go from here is a question.  The choices here are among 6 sets of starting digits.  If we follow through each of these by trial division, at each stage there are more choices.  This is unfortunate from the point of view of finding the correct sequence of choices, but the great variety does assure us there is likely a solution, as, when we get to the last 23 digits, they have to come out as consisting solely of 7's and 6's, and there are 2^23=8,388,608 such 23-digit numbers, out of 10^23 23-digit numbers altogether. If there are 6 possibilities each step of the way of trial divisions, they multiply to a 40-digit number by the time you've chosen 52 digits for the multiplier.

Posted by Charlie on 2004-03-14 12:16:18