wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Two Face Bomb
        
(Message started by: Maestro on May 21st, 2007, 9:13pm)
Title: Two Face Bomb
Post by Maestro on May 21st, 2007, 9:13pm
I'm curious if I am close..originally I thought Two Face could flip his coin 1000 times side A would be a '21' and side B '12' ...this is not very timely though so to be equally random 2000 digit code using 1s and 2s he could generate it in 2 flips of his coin. Side A: 1000 digits starting with 1: 12121212..etc Side B: 1000 digits starting with 2: 21212121..etc. This could be used with any sequence of numbers as long as it's comprised of half 1s and half 2s..ie 22112211..
Title: Re: Two Face Bomb
Post by towr on May 22nd, 2007, 12:12am
That does not not very random though..
Unless I misunderstand what you're doing, then in the first case, half the digits determine the other half.
Title: Re: Two Face Bomb
Post by Icarus on May 22nd, 2007, 5:14pm
One thing to consider: How many codes are there with equal numbers of 1s and 2s?
Title: Re: Two Face Bomb
Post by Maestro on May 23rd, 2007, 8:48pm
:-/ I was unable to create a formula for how many uniform(equal 1s and 2s) codes there are in 2^n though if I had I'm not sure what help it would be.. 2^4 has 6, 2^8 has 70. So I resorted to simply TwoFace must flip his coin 1000 times minimum, to be completely random, or until he hits one side or the other 1000 times at which point the rest of his code will be obvious....
Title: Re: Two Face Bomb
Post by Icarus on May 23rd, 2007, 9:12pm
If I gave you a list of 128 items to choose from, would it take you 64 flips of your coin to make a random choice? No. You could do it with 7 flips.

Likewise, the minimum number of flips Two-Face needs is log2 N rounded up to the nearest integer, where N is the number of codes with equal 1s and 2s.
Title: Re: Two Face Bomb
Post by Eigenray on May 23rd, 2007, 9:48pm
It's not possible using a bounded number of flips.  A relatively simple method uses about 3495 flips on average, but it is possible to do it using an average of

1995.58173582321330482153...

flips.  Can this be improved?

(Where does the above number come from, and why is it rational?)
Title: Re: Two Face Bomb
Post by Eigenray on May 24th, 2007, 2:22am
If we're allowed to use a biased coin (with probability [hide]0.49964...[/hide] of heads) then it can be done in exactly [hide]4000[/hide] flips.  Can this be improved?  Probably, but I'd guess that the computations required to find the true optimal solution would be too unwieldy.
Title: Re: Two Face Bomb
Post by Eigenray on May 24th, 2007, 4:05am
Since not everyone can easily work with 601-digit numbers, let's start small.

Suppose we have to use a fair coin to choose between n possibilities, with each outcome equally likely.  For n=1,2,3,...,16, it can be done with expected number of flips:

{0, 1, 8/3, 2, 18/5, 11/3, 24/7, 3, 14/3, 23/5, 160/33, 14/3, 306/65, 31/7, 64/15, 4}

1) What method am I using?

2) If F(n) is the average number of flips using this method, show that F(n) < 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif for all n.  Attached is a plot of F(n) - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif.

3) Does this method minimize the expected number of flips?

4) Is there a "closed form" for F(n)?  (More closed than the definition, that is.)
Title: Re: Two Face Bomb
Post by towr on May 24th, 2007, 4:09am

on 05/23/07 at 21:48:43, Eigenray wrote:
A relatively simple method uses about 3495 flips on average, but it is possible to do it using an average of

1995.58173582321330482153...

flips.  Can this be improved?
If that's log2 nchoosek(2000,1000), then no.
Title: Re: Two Face Bomb
Post by Eigenray on May 24th, 2007, 4:43am

on 05/24/07 at 04:09:54, towr wrote:
If that's log2 nchoosek(2000,1000), then no.

log2 C(2000,1000) = 1994.19...

Any method must use at least 1995 flips on each run, because with 1994 flips, the resolution is only 1/21994 > 1/C(2000,1000).  So the expected number of flips must be at least 1995 (in fact, strictly greater).


We may think of an infinite binary tree.  For a node v at level L(v), give the subtree [v] below it measure 2-L(v).  We need to partition this tree into n sets, each of which is a disjoint union of subtrees with total measure 1/n.  And we wish to minimize http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif L(v)2-L(v), where the sum is over all subtrees [v] in the collection.
Title: Re: Two Face Bomb
Post by towr on May 24th, 2007, 7:32am

on 05/24/07 at 04:05:36, Eigenray wrote:
{0, 1, 8/3, 2, 18/5, 11/3, 24/7, 3, 14/3, 23/5, 160/33, 14/3, 306/65, 31/7, 64/15, 4}
The best I can seem to do for n=5 is 22/5; f = 5/8*3 + 1/8*(3+f) + 2/8*(2+f) -> f= 22/5
Likewise I find different values for some of the others. Am I using a different method or is something else afoot?

[edit]nevermind, I found how to get 18/5
f=10/16*3+5/16*4+1/16(4+f) -> f=54/15=18/5[/edit]
Title: Re: Two Face Bomb
Post by Barukh on May 24th, 2007, 11:44am

on 05/24/07 at 04:05:36, Eigenray wrote:
1) What method am I using?

n = 11: [11/16] [11/64] [11/128] [11/256] [11/1024] [1/1024...][/quote]


Quote:
2) If F(n) is the average number of flips using this method, show that F(n) < 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif for all n.  Attached is a plot of F(n) - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif.

F(2n) = F(n) + 1.


Quote:
3) Does this method minimize the expected number of flips?

???
Title: Re: Two Face Bomb
Post by Eigenray on May 24th, 2007, 1:40pm

on 05/24/07 at 07:32:48, towr wrote:
f=10/16*3+5/16*4+1/16(4+f) -> f=54/15=18/5

on 05/24/07 at 11:44:51, Barukh wrote:
n = 11: [11/16] [11/64] [11/128] [11/256] [11/1024] [1/1024...]

Yes, that's it.  Define

r0 = 1;  k0 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif
r1 = 2k0r0 - n;  k1 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n/r1)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif
r2 = 2k1r1 - n;  k2 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n/r2)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif
ri+1 = 2kiri - n;  ki+1 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n/ri+1)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif

Then

F(n) = k0 + r1/(n+r1) [ k1 + r2/(n+r2) [ k2 + r3/(n+r3) [ k3 + ...
= k0 + k1 r1/2k0 + k2 r2/2k0+k1 + k3 r3/2k0+k1+k2 + ...
= s0 + k1<2s0> + k2<2s1> + k3<2s2> + ...,

where si=k0+...+ki and <m> = (m mod n)/m.  (Since ri, ki are periodic, F(n) is rational.)


Quote:
F(2n) = F(n) + 1.

Yes, but what about odd n?

I updated the graph.  How do you explain the dashed lines located 1/3 and 3/5 of the way into each interval between powers of 2?  (I realized their significance while proving the result.)  Does the graph converge in some sense?  To what?


Quote:
???

I don't know either.
Title: Re: Two Face Bomb
Post by Eigenray on May 25th, 2007, 1:28am
As n goes to infinity, F(2nx) - n should depend only on x in (1/2, 1).  This limiting function g satisfies

g(x) = (1-x)( k + g(x') ),

where k = [log2(x/(1-x))], and x' = x/(1-x) / 2k.  ([] denotes ceiling.)

So I used the following iterated function system to plot the limiting graph (I like making graphs):

Pick k=1,2,3,... via k=[log2((1+u)/(1-u))], where u is uniform (0,1).  Then perform

x' = x/(x+2-k)
y' = (1-x) ( k +y ).

For some reason I plotted vs 1-x instead of x.  In blue is the function f1(x) = (1-x)k, and in purple is f2(x) = (1-x)( k + (1-x')k'), where k = [log2(x/(1-x))], and x' = x/(1-x) / 2k.
Title: Re: Two Face Bomb
Post by Barukh on May 25th, 2007, 7:01am
I used a slightly different approach.

Let n be an odd number, and m satisfies 2m – 1 = nq. Write a binary expansion of q:
q = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifi=0…s(q) qi2i,


where s(q) = |_log(q)_|.

Then the expected number of throws F(n) – using the method under discussion – satisfies:

F(n) = nhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifi (m-i)qi2i-m + (m+F(n)) / 2m,

or
F(n) = m + m/nq - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifi iqi2i / q


I think this may be used to prove the bound in 2), but don’t see yet how.
Title: Re: Two Face Bomb
Post by Grimbal on May 25th, 2007, 9:17am

on 05/24/07 at 04:05:36, Eigenray wrote:
Suppose we have to use a fair coin to choose between n possibilities, with each outcome equally likely.  For n=1,2,3,...,16, it can be done with expected number of flips:

{0, 1, 8/3, 2, 18/5, 11/3, 24/7, 3, 14/3, 23/5, 160/33, 14/3, 306/65, 31/7, 64/15, 4}

1) What method am I using?


I don't know, but with some simulations I find the same numbers.

{ 0/1, 2/2, 8/3, 8/4, 18/5, 22/6, 24/7, 24/8, 42/9, 46/10, 160/3/11, 56/12, 306/5/13, 62/14, 64/15, 64/16, 98/17, 102/18, 2936/27/19, 112/20, 114/21, 386/3/22, 11672/89/23, 408/3/24 }

I don't see a closed form to that sequence, except for n that seems to appear in the denominator.

Anyway, my method is as follows:
Flip the coin to create enough outcomes to reach or exceed n.  When you exceed n, you use up n outcomes to make a choice and recycle the unused m=2k-n outcomes.  You continue flipping, giving 2·m, 4·m, until you exceed again.  etc.
Counting the coin flips and taking into account the probability to stop each time you exceed n, it converges to the values found above.  I converted them manually to fractions.
Title: Re: Two Face Bomb
Post by Eigenray on May 25th, 2007, 12:48pm

on 05/25/07 at 09:17:35, Grimbal wrote:
Flip the coin to create enough outcomes to reach or exceed n.  When you exceed n, you use up n outcomes to make a choice and recycle the unused m=2k-n outcomes.  You continue flipping, giving 2·m, 4·m, until you exceed again.  etc.
Counting the coin flips and taking into account the probability to stop each time you exceed n, it converges to the values found above.  I converted them manually to fractions.

That's what I did at first.  But if you restrict yourself to odd n, eventually (after s flips, say) m will be 1, and the whole thing starts over, so F(n) = blah + F(n)/2s.  I used:

Code:
F[n_] := F[n] = Module[{r, k, e, s},
       If[Mod[n, 2] == 0, Return[F[n/2] + 1]];
       {r, k, e, s} = {1, 0, 0, 0};
       While[True,
         k = Ceiling[Log[2, n/r]];
         e += k r/2^s;
         s += k;
         r = 2^k r - n;
         If[r == 1, Return[e/(1 - 1/2^s)]];
       ];
     ];
F[1] = 0;
Title: Re: Two Face Bomb
Post by Eigenray on May 25th, 2007, 2:14pm

on 05/25/07 at 07:01:31, Barukh wrote:
E(n) = m + m/nq - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifi iqi2i / q

Ah, that's nice.  That's probably as closed form as it gets.  So what is E(C(2000,1000))? :P

Thinking of the binary expansion of

1/n = (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif qi/2m-i) (1 + 1/2m + 1/22m + ...),

your formula says that if

1 = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifS n/2i

for some (unique, if n isn't a power of 2) subset S of N={1,2,3,...}, then

E(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifS i n/2i.

In hindsight, this is clear if you think of the expected value of the height when you partition the infinite binary tree into n equal parts.  For i in S, you have n subtrees at level i, of total measure n/2i.

I hadn't realized this before, in my previous expression [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?action=display;board=riddles_hard;num=1179807186;start=0#12]here[/link], which can be rewritten as

F(n) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (si+1-si)[ 2si mod n ]/2si,


then {si} is precisely the set S above.  This is because 2k[ 2s mod n ] first passes n precisely when the (s+k)'th digit of 1/n is a 1.
Title: Re: Two Face Bomb
Post by Barukh on May 27th, 2007, 4:08am

on 05/24/07 at 04:05:36, Eigenray wrote:
2) If F(n) is the average number of flips using this method, show that F(n) < 1+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif for all n.

Ah, I just realized that I used a different notation for F(n). Changed the previous post.

Let’s evaluate (where i runs from 0 to s(q), j runs from 0 to s(q) – 2):

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifi iqi2i – (s(q)-1)q =
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifi (i+1)qi2i – s(q)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifi qi2i =
2s(q) - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifj (s(q)-j-1)qj2j >
2s(q) - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifj (s(q)-j-1)2j =
2s(q) – (2s(q) – s(q) – 1) =
s(q) + 1.


Likewise s(q), define s(n) = |_ log(n) _|. Then, clearly, s(n) + s(q) = m – 1. Also,  m < n. Collecting all this,

F(n) = m + m/nq - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifi iqi2i / q < m + 1/q – (s(q)-1) – (s(q)+1)/q < m – s(q) + 1 = s(n) + 2,

which establishes the result.
Title: Re: Two Face Bomb
Post by Eigenray on May 27th, 2007, 8:30pm
That's interesting, because it's so different from my idea, which is a sort of bootstrapping argument.  Using my previous notation, and setting ui = n/ri > 1, we have

F(n) - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(n)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdelta.gif(u1,u2,...) = 1/(u1+1)(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(u1)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif + 1/(u2+1)(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(u2)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif + 1/(u3+1)(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(u3)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif +...
= h(u1) + 1/(u1+1)(h(u2) + 1/(u2+1)(h(u3) + ...,

where h(u) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(u)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif/(u+1).  Since http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2(u)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gifis locally constant, and 1/(u+1) is decreasing,

sup h(u) = max{1/2, 2/3, 3/5, 4/9, ...} = 2/3.

Now let C be the supremum of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdelta.gif(ui), over all possible sequences of ui>1.  Since h(u)<2/3 for all such u,

C http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 2/3 + 1/2*(2/3) + 1/22*(2/3) +... = 4/3,

so C is finite.  Now we can use C to bound itself:

C = supu {(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.giflog2uhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif+ C)/(1+u)},
= max { (C+1)/2, (C+2)/3, (C+3)/5, (C+4)/9, ... }
= (C+1)/2,

where the last equality is because C http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 1.  Therefore C=1.  So http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdelta.gif gets arbitrarily close to 1, but it is always strictly less, since

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdelta.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif h(u) + 1/(u+1) < 1.


But when exactly is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cdelta.gif close to 1?  We get close to 1 if each (or at least the first few) ui is slightly greater than either 1 or 2.  (But for any odd n we'll eventually have some ui=n, or more generally, ui=oddpart(n).)

u1 = n/r1 ~ 1  when r1 = 2k - n ~ n,

so u1 is slighty more than 1 when n is slightly more than a power of 2.  And similarly, u1 ~ 2 when 2k - n ~ n/2, or when n is slightly more than 2/3*2k, which is to say, just past 1/3 of the way between 2k-1 and 2k.

This is why the limiting graph, between 2k-1 and 2k, goes to 1 just past 2k-1 and 2k-1*4/3.

And for t=2,3,..., we have smaller and smaller jumps when u1 = 2t+http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif, or when n = 2k(1 - 1/(2t+1)) + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/epsilon.gif.
Title: Re: Two Face Bomb
Post by Barukh on May 30th, 2007, 4:09am

on 05/25/07 at 14:14:48, Eigenray wrote:
So what is F(C(2000,1000))? :P

If I didn't make a mistake, s(n) = 1995, m = 230291915544904137854586519173339676376633611759003396244800.

That means q contains more than 2.3*1060 bits...

::)

BTW, here (http://portal.acm.org/citation.cfm?id=1070432.1070587) is an interesting relevant article (please let me know if you want the full text and cannot access it).
Title: Re: Two Face Bomb
Post by Eigenray on May 30th, 2007, 11:12am

on 05/30/07 at 04:09:28, Barukh wrote:
If I didn't make a mistake, s(n) = 1995, m = 230291915544904137854586519173339676376633611759003396244800.

Mathematica tells me MultiplicativeOrder[2,Binomial[2000,1000]/2^6] is

854522991837209344268722058805491173276383424051222219160883928360175636974907\
256821410761405900488073841655380987349144864850893678186613504750839983625728\
1542017600.

For your m, I get

PowerMod[2, m, #]&/@(Transpose[FactorInteger[Binomial[2000, 1000]/2^6][1])

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 626, 1, 1, 1, 1, 1, 1, 750, 99, 1, 620, 258, 1, 328, 1, 966, 1, 1, 1, 1, 1, 1, 1, 581, 151, 883, 1, 1, 1, 1, 858, 762, 1, 1, 1, 1, 1, 282, 1, 1, 931, 1, 1, 352, 848, 1, 1, 1, 1176, 565, 1, 166, 1, 1262, 1, 1, 1, 490, 1369, 1, 69, 1168, 1263, 1, 1, 1186, 1, 639, 1, 781, 281, 1, 1142, 1, 1, 823, 1, 1281, 1528, 1353, 1, 1, 209, 1, 1, 863, 1436, 1069, 540, 1, 1135, 970, 1, 1, 1267, 1529, 1, 1, 538, 90, 1, 1, 467, 1, 1, 1589, 1, 829, 1, 1587, 606, 1, 1, 1, 1596, 1, 1, 1, 1097, 1310, 1, 733, 602, 1589, 1, 1637, 1, 1, 1, 1020, 1, 1533, 1},

which is close (although I wrote my own PowerMod since Mathematica 5.0's is unreliable).


Quote:
BTW, here (http://portal.acm.org/citation.cfm?id=1070432.1070587) is an interesting relevant article (please let me know if you want the full text and cannot access it).

That is interesting, but they only seem to be concerned with approximating a coin of bias r given a coin of bias p.


Quote:
In Section 3, when the bias of the source is known, we establish the difficulty of finding optimal algorithms.  Knuth and Yao [13] represented their algorithms by binary trees called discrete distribution generation trees (DDG-trees). We generalize the DDG-tree so that we can represent algorithms for biased sources. All algorithms that we cited previously [19, 10, 8, 13, 18, 7, 16, 7, 1, 9] can be represented as DDG-trees. We define a model of recursive construction of DDG-trees based on the algebraic decision tree. This model of computation captures all previously known algorithms [13, 1, 9] for this problem. For this model of computation, we use a topological argument to prove that constructing an optimal DDG-tree for a source of known bias is impossible.


This looks even more relevent:

Quote:
Knuth and Yao [13] devised an elegant method to simulate a given discrete probability distribution using a fair coin with an optimal efficiency.
[13] D. E. Knuth and A. C.-C. Yao. The complexity of nonuniform random number generation. In J. F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results. Proceedings of a Symposium, pages 357-428, New York NY, 1976. Carnegie-Mellon University, Computer Science Department, Academic Press.

But I will have to go to campus to read it.
Title: Re: Two Face Bomb
Post by Barukh on May 31st, 2007, 1:30am

on 05/30/07 at 04:09:28, Barukh wrote:
If I didn't make a mistake, s(n) = 1995, m = 230291915544904137854586519173339676376633611759003396244800.

Of course, I did! After fixing, I get the same number as Eigenray’s.

Unfortunately (or fortunately?) I don’t have Mathematica at my disposal. So, I used simpler tools available to compute m. Here’s what I did:

1. Factorize C(2000, 1000)  = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif piei (this is easy).

2. For every odd pi, find mi - the multiplicative order of 2 mod piei (equivalently: find the discrete logarithm of 1 to base 2 in Z/piei). I did it brute force (C program), which is not too bad taking into account small modules. (BTW: are there more efficient ways to compute this for arbitrary modules and bases?)

3. Compute lcm of all the mi-s in the form http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif qifi, which is also easy.

4. Get the result by multiplying (used this (http://www.alpertron.com.ar/ECM.HTM) resource).

Ah, and also s(n) = 1994.
Title: Re: Two Face Bomb
Post by Eigenray on May 31st, 2007, 12:47pm

on 05/31/07 at 01:30:14, Barukh wrote:
2. For every odd pi, find mi - the multiplicative order of 2 mod piei (equivalently: find the discrete logarithm of 1 to base 2 in Z/piei). I did it brute force (C program), which is not too bad taking into account small modules. (BTW: are there more efficient ways to compute this for arbitrary modules and bases?)

To compute the order of a mod pk, first compute the order r of a mod p.  If pt is the largest power of p dividing ar-1, then for k>t, the order of a mod pk is pk-tr, if p is odd.

But in general, finding multiplicative orders efficiently is equivalent to factoring efficiently.

If we can factor phi(n), then just walk down the poset of divisors of phi(n) to find a minimial element with ak=1.

And conversely, well, that sounds like a good problem.
Title: Re: Two Face Bomb
Post by SWF on May 31st, 2007, 8:25pm
I am having a hard time following what the question is here.  I think it is the same as the old thread Two face: How's this answer (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1033240646).


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board