Author |
Topic: Two Face Bomb (Read 2711 times) |
|
Maestro
Newbie
I dare do all that may become a man
Gender: 
Posts: 3
|
 |
Two Face Bomb
« on: May 21st, 2007, 9:13pm » |
 Quote  Modify
|
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..
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Two Face Bomb
« Reply #1 on: May 22nd, 2007, 12:12am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Two Face Bomb
« Reply #2 on: May 22nd, 2007, 5:14pm » |
Quote Modify
|
One thing to consider: How many codes are there with equal numbers of 1s and 2s?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Maestro
Newbie
I dare do all that may become a man
Gender:
Posts: 3
|
|
Re: Two Face Bomb
« Reply #3 on: May 23rd, 2007, 8:48pm » |
Quote Modify
|
 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....
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Two Face Bomb
« Reply #4 on: May 23rd, 2007, 9:12pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Two Face Bomb
« Reply #5 on: May 23rd, 2007, 9:48pm » |
Quote Modify
|
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?)
|
| « Last Edit: May 24th, 2007, 4:06am by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Two Face Bomb
« Reply #6 on: May 24th, 2007, 2:22am » |
Quote Modify
|
If we're allowed to use a biased coin (with probability 0.49964... of heads) then it can be done in exactly 4000 flips. Can this be improved? Probably, but I'd guess that the computations required to find the true optimal solution would be too unwieldy.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
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+ log2(n) for all n. Attached is a plot of F(n) - log2(n).
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.)
|
| « Last Edit: May 24th, 2007, 12:44pm by Eigenray » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Two Face Bomb
« Reply #8 on: May 24th, 2007, 4:09am » |
Quote Modify
|
on May 23rd, 2007, 9:48pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Two Face Bomb
« Reply #9 on: May 24th, 2007, 4:43am » |
Quote Modify
|
on May 24th, 2007, 4:09am, 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  L(v)2-L(v), where the sum is over all subtrees [v] in the collection.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Two Face Bomb
« Reply #10 on: May 24th, 2007, 7:32am » |
Quote Modify
|
on May 24th, 2007, 4:05am, 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]
|
| « Last Edit: May 24th, 2007, 8:02am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Two Face Bomb
« Reply #11 on: May 24th, 2007, 11:44am » |
Quote Modify
|
on May 24th, 2007, 4:05am, 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+log2(n) for all n. Attached is a plot of F(n) - log2(n). |
|
F(2n) = F(n) + 1.
Quote:| 3) Does this method minimize the expected number of flips? |
|
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Two Face Bomb
« Reply #12 on: May 24th, 2007, 1:40pm » |
Quote Modify
|
on May 24th, 2007, 7:32am, towr wrote:| f=10/16*3+5/16*4+1/16(4+f) -> f=54/15=18/5 |
|
on May 24th, 2007, 11:44am, Barukh wrote:
n = 11: [11/16] [11/64] [11/128] [11/256] [11/1024] [1/1024...] |
|
Yes, that's it. Define
r0 = 1; k0 = log2(n)
r1 = 2k0r0 - n; k1 = log2(n/r1)
r2 = 2k1r1 - n; k2 = log2(n/r2)
ri+1 = 2kiri - n; ki+1 = log2(n/ri+1)
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:
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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Two Face Bomb
« Reply #14 on: May 25th, 2007, 7:01am » |
Quote Modify
|
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 = i=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) = ni (m-i)qi2i-m + (m+F(n)) / 2m,
or
F(n) = m + m/nq - i iqi2i / q
I think this may be used to prove the bound in 2), but don’t see yet how.
|
| « Last Edit: May 27th, 2007, 4:12am by Barukh » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Two Face Bomb
« Reply #15 on: May 25th, 2007, 9:17am » |
Quote Modify
|
on May 24th, 2007, 4:05am, 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.
|
| « Last Edit: May 26th, 2007, 3:43am by Grimbal » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Two Face Bomb
« Reply #16 on: May 25th, 2007, 12:48pm » |
Quote Modify
|
on May 25th, 2007, 9:17am, 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; |
|
|
| « Last Edit: May 25th, 2007, 2:38pm by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Two Face Bomb
« Reply #17 on: May 25th, 2007, 2:14pm » |
Quote Modify
|
on May 25th, 2007, 7:01am, Barukh wrote:| E(n) = m + m/nq - i iqi2i / q |
|
Ah, that's nice. That's probably as closed form as it gets. So what is E(C(2000,1000))? 
Thinking of the binary expansion of
1/n = ( qi/2m-i) (1 + 1/2m + 1/22m + ...),
your formula says that if
1 = S n/2i
for some (unique, if n isn't a power of 2) subset S of N={1,2,3,...}, then
E(n) = S 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 here, which can be rewritten as
F(n) = (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.
|
| « Last Edit: May 25th, 2007, 2:33pm by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Two Face Bomb
« Reply #18 on: May 27th, 2007, 4:08am » |
Quote Modify
|
on May 24th, 2007, 4:05am, Eigenray wrote:| 2) If F(n) is the average number of flips using this method, show that F(n) < 1+log2(n) 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):
i iqi2i – (s(q)-1)q =
i (i+1)qi2i – s(q)i qi2i =
2s(q) - j (s(q)-j-1)qj2j >
2s(q) - j (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 - i iqi2i / q < m + 1/q – (s(q)-1) – (s(q)+1)/q < m – s(q) + 1 = s(n) + 2,
which establishes the result.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Two Face Bomb
« Reply #19 on: May 27th, 2007, 8:30pm » |
Quote Modify
|
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) - log2(n) =  (u1,u2,...) = 1/(u1+1)(log2(u1) + 1/(u2+1)(log2(u2) + 1/(u3+1)(log2(u3) +...
= h(u1) + 1/(u1+1)(h(u2) + 1/(u2+1)(h(u3) + ...,
where h(u) = log2(u)/(u+1). Since log2(u)is 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 (ui), over all possible sequences of ui>1. Since h(u)<2/3 for all such u,
C  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 {(log2u+ 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  1. Therefore C=1. So gets arbitrarily close to 1, but it is always strictly less, since
h(u) + 1/(u+1) < 1.
But when exactly is 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+ , or when n = 2k(1 - 1/(2t+1)) + .
|
| « Last Edit: May 27th, 2007, 8:44pm by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Two Face Bomb
« Reply #20 on: May 30th, 2007, 4:09am » |
Quote Modify
|
on May 25th, 2007, 2:14pm, Eigenray wrote:| So what is F(C(2000,1000))? |
|
If I didn't make a mistake, s(n) = 1995, m = 230291915544904137854586519173339676376633611759003396244800.
That means q contains more than 2.3*1060 bits...
BTW, here is an interesting relevant article (please let me know if you want the full text and cannot access it).
|
| « Last Edit: May 30th, 2007, 8:36am by Barukh » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Two Face Bomb
« Reply #21 on: May 30th, 2007, 11:12am » |
Quote Modify
|
on May 30th, 2007, 4:09am, 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
854522991837209344268722058805491173276383424051222219160883928360175636 974907\
256821410761405900488073841655380987349144864850893678186613504750839983 625728\
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 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.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Two Face Bomb
« Reply #22 on: May 31st, 2007, 1:30am » |
Quote Modify
|
on May 30th, 2007, 4:09am, 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) =  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 qifi, which is also easy.
4. Get the result by multiplying (used this resource).
Ah, and also s(n) = 1994.
|
| « Last Edit: May 31st, 2007, 1:31am by Barukh » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Two Face Bomb
« Reply #23 on: May 31st, 2007, 12:47pm » |
Quote Modify
|
on May 31st, 2007, 1:30am, 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.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Two Face Bomb
« Reply #24 on: May 31st, 2007, 8:25pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print