Powers of 2

In other words, we want to solve the equation

2^n == 1048576 (mod 10000000)

We start by noting that 10000000 is divisible by 2^7, so this simplifies to

2^(n-7) == 8192 (mod 78125)

Since 20 is a solution to this, any other solution n > 20 must tell us that 2^(n-20) == 1 (mod 78125). So we are after the smallest power of two congruent to 1 mod 78125.

78125 is (by construction) 5^7, so there are phi(5^7) = 4*5^6 = 62500 numbers in the range [0,78125) coprime to 78125. Thus we can immediately know (Fermat-Euler theorem) that 2^62500 is congruent to 1 mod 78125. The remaining question is whether that's the _smallest_ solution. We can test this easily: if 2^x == 1 mod 78125 for some 0 < x < 62500, then x must divide 62500 and also divide some 62500/k where k is a prime factor of 62500. So we need only divide 62500 by each of its prime factors to get 12500 and 31250, and test each of those. It turns out that neither 2^12500 nor 2^31250 is congruent to 1 mod 78125, and hence 2 is a primitive root mod 78125 - so there is no solution smaller than the one we already have.

So 2^62500 is the smallest non-zero power of two congruent to 1 mod

78125, and hence 2^62520 is the first power of 2 to end in 1048576 after 2^20.

--
Simon Tatham         "_shin_, n. An ingenious device for 
    finding tables and chairs in the dark."

"Simon Tatham" schrieb im Newsbeitrag news:nZp* snipped-for-privacy@news.chiark.greenend.org.uk...

I see the mathematical proof and I really like it (nice work, Simon!). But, having studied Computer Science, I know two ways to solve a problem like this. I really like a mathematical proof, but in 99 of 100 cases I think: This can be solved by a computer program, written in a two minutes, solved in a few seconds. And it will get the correct result, whereas the mathematical proof MIGHT have a logical error. So I go:

#include

void main () { long cnt=20; long l=1048576;

do { l = l * 2; l = l % 10000000; cnt++; } while (l != 1048576);

printf ("2^%d\n", cnt); }

compile it, run it, and get the desired result "2^62520" in less than a second.

I don't know why I would never think about solving it the mathematical way if programming is an option. I ALWAYS preferred programming because there remains no doubt that I might have missed a number (because I tried every single number between 20 and 62520).

If the numbers were getting larger, I would think about ways to further improve computing time, but still would not switch to Mathematics if I see any chance to solve it by programming.

Can anyone understand me? What would be needed to convince me to try it with Mathematics right from the start?

\/ `/ `|´ | `´ \´ ``´

In that case I should probably admit that I did write a similar program first, and once I knew what the answer was _then_ I wrote my proof :-)

The advantage of the number-theoretic approach is that it scales up more readily than simple iteration. Suppose the original poster now turns round and asks for the next power of two above 2^128 which ends in 340282366920938463463374607431768211456? The obvious search algorithm will now take an astronomically long time, whereas a technique derived from my proof ought to be able to produce the answer in a few seconds. If I needed answers to a lot of questions of this type, I'd write a program which followed the structure of my proof, computing gcds and phi-functions and finding the order of elements in groups, and it would still be giving near-instantaneous answers for much larger numbers.

It is true that a complicated piece of mathematics is more prone to subtle errors than an easily verifiable linear search program. That's why I tried both methods and made sure they agreed :-)

--
Simon Tatham         "loop, infinite _see_ infinite loop" 
     - Index, Borland Pascal Language Guide

Oh, and one more thing: the point of puzzles is to have fun, not just to get the answer. The programmatic search gives the answer, but personally I didn't actually care what the answer was. Working out the proof, on the other hand, was _fun_!

--
Simon Tatham         "_shin_, n. An ingenious device for 
    finding tables and chairs in the dark."

But that's the point of writing the program - it's the writing (and running, giving instant answers effortlessly) - that's the fun part. ;-)

Cheers! Rich

Depends on the program. This program was far too simple to be any fun to write, whereas the proof was complex enough to be interesting.

Writing a program to solve the blindfolded bottle-inversion puzzle, on the other hand, or the two-inverter logic gates puzzle ... _those_ were fun.

--
Simon Tatham         "loop, infinite _see_ infinite loop" 
     - Index, Borland Pascal Language Guide

"Two inverter logic gates puzzle?" I haven't heard of it. Is it in the FAQ? Speaking of which, where might one find a FAQ?

Thanks, Rich

It's a problem in digital electronics. The challenge is to design a logic circuit which takes three inputs A,B,C, and outputs their inversions ~A,~B,~C; the restriction is that although you may use as many AND and OR gates as you like, you're allowed only two NOT gates.

(And - of course - no NANDs, NORs, XOR with 1 or anything cheating like that. Two straight NOT gates are the only non-increasing functions you may use.)

I would start by googling for `rec.puzzles FAQ', which curiously turns out to produce a plausible-looking page as only the _second_ hit. I don't see this puzzle in there.

(The first hit was labelled `rec.puzzles archive', which might have been a better place to look for a particular puzzle if it hadn't given me a strange database error when I tried to visit the site. Oh well.)

--
Simon Tatham         "A defensive weapon is one with my finger on the 
    trigger. An offensive weapon is one with yours."

Kewl! I've crossposted this, because I bet some electronic geek will solve it in minutes! ;-)

So far, I have no clue, but I'm ass-u-me-ing that DeMorgan's theorem fits in there somewhere.

Electronics guys: When you solve this, leave spoiler space, OK?

Thanks! Rich

Well, electronic guys would NEVER solve this using the solution Ed Murphy posted... . . . . because... . . . . just... . . . . like... . . . . spoiler... . . . . space,... . . . . that... . . . . solution... . . . . creates... . . . . excessive propagation delay. 9 gates worth!

n1 gets ANDed with a 4-gate delayed version of itself. We're talking serious glitches here. And take it from someone who has solved such problems in real circuits, propagation delay glitches are NO fun to track down.

The electronics guy would simply glue a 7404 to the board on its back, leads in the air and wire it in using wire wrap wire.

The electronic guy from the 70's perhaps...

Today he would probably use a 74VHC04 or 74ALS04 or similar and the 1ns delay with those guys aren't that bad !

;-)

Nope. He would look at the odd free pins on his GAL and revise its programming slightly.

--
"If you want to post a followup via groups.google.com, don\'t use
 the broken "Reply" link at the bottom of the article.  Click on 
 "show options" at the top of the article, then click on the 
 "Reply" at the bottom of the article headers." - Keith Thompson
More details at: 
Also see

And in the 70's, we didn't have circuits operating at GHz clock rates. Let's see, 1 ns is 0.000000001 sec which corresponds to a clock cycle of ONLY 1 GHz. Sounds like I'm not the only one stuck in the past.

And even in the 70's, a 1 ns glitch could cause havoc if connected to an edge triggered flip-flop input such as the clock or reset. In fact, for the particular case I had in mind, the glitch was less than 1 ns. It was in every circuit (due to foolish logic design) and only worked at all because the glitch never quite made it to the logic threshold. Unless one of the gates involved was a little bit slower than average. And even then, it would only create a problem when doing hardware division on 14-digit operands. That one was a lot of fun.

And rather than fixing the circuit, they hired a consultant to write a comprehensive diagnostic program to test just about every possible combination of operand patterns and lengths so that the out of spec chips could be spotted.

Finagle! Sounds like a classic case of marginal design resulting in problems that are management solved by stupendously nitpicky enforcement of procurement contracts; in order to comply with the company's (frozen design) contract. Right out of the old cost plus days.

--
JosephKK
Gegen dummheit kampfen die Gotter Selbst, vergebens.  
--Schiller