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

Working from the right, the problem is not quite as bad as working from the left, but at each stage in choosing a multiplier, you are presented with two choices of a digit.  For example, here's one where the only choice of 6 was at the rightmost position; from there on only 1 was chosen to produce a 6 in the product:

916     69211003172937520251928576
9116    688785485725434972288843776
93116   7035646038702238139496267776
943116          71259830205729413045761867776
9243116         698390099130818297424590667776
90243116        6818577060929878494374606667776
900243116       68020446678920480463874766667776
9400243116      710262288349192229526530766667776
90400243116     6830449250148252426476546766667776
910400243116    68787897505397997630168066766667776
9010400243116   680806593685304017325169666766667776
92010400243116          6952109282936192861113457666766667776
912010400243116         68909557538185938064804977666766667776

where the left number is the multiple and the right is the product up to that point as we build the multiplier from right to left.

Another set of choices looks like this:

66      4986819005910345345662976
866     65433109986641804080971776
6866    518780292342127744595787776
86866   6563409390415273618126667776
586866          44342341253372435327694667776
7586866         573247387334772699261646667776
77586866        5862297848148775338601166667776
677586866       51197016083697369390082766667776
9677586866      731217789616926280162306766667776
69677586866     5264689613171785685310466766667776
769677586866    58155194221311812078705666766667776
7769677586866   587060240302712076012657666766667776
77769677586866          5876110701116714715352177666766667776

but the resulting set of digits in the product is still the same.

In fact the same set is produced by randomly choosing which of the two should be used at each step:

 916     69211003172937520251928576
 616     46543644055163223226187776
 90616   6846751379387452330948427776
 930616          70315356909155484003022667776
 930616          70315356909155484003022667776
 94930616        7172754547145101885401806667776
 904930616       68374624165135703854901966667776
 704930616       53263051419952839171074766667776
 7704930616      582168097501353103105026766667776
 97704930616     7382375832833642210827266766667776
 9497704930616   717626294856428282350705666766667776
 91497704930616          6913371120381402802719857666766667776
 911497704930616         68870819375631148006411377666766667776

So what if we continue?

At the end we get:

60323785355017521615381548200199638897190843742219575360695242527202826527017533487543311497704930616  

which multiple of 2^76 is

4557936353285720092883266666766767776667766777666667776766677767667676666776766667777767666677766776777777777777666766667776

and if we take the last 76 digits of this, the result is indeed divisible by 2^76, and so is the answer:

6667776766677767667676666776766667777767666677766776777777777777666766667776

Edited on March 14, 2004, 1:49 pm

Edited on March 14, 2004, 1:53 pm

Posted by Charlie on 2004-03-14 13:48:25