December 2002 - mathfun@mailman.xmission.com

[math-fun] Re: Your discrete log question
by Mike Stay 24 Dec '02

24 Dec '02

Sorry, you're right! I forgot to say that the p's are primes. OK, let me try again with less cumbersome notation (although my question was mostly about how to make the notation better in the first place...) Pick p,q primes > some composite n. Make sure (p-1) and (q-1) are smooth so that one can use the Pohlig-Hellman algorithm to calculate discrete logs. Also choose them so they both have g as a generator; that is, the powers of the element g give every number mod p and mod q except 0. Let lg_p, p prime, be discrete log base g over p; that is, find x given y,p in the equation y=g^x mod p. Then x=lg_p(y). Let a(x,p) = g^(lg_p(n) - lg_p(x)) mod p Then find x != 1,n such that a(x,p) == a(x,q) The idea is that only factors of n satisfy both sides simultaneously. (I haven't proven that.) It's a strange problem, I think, because it's easy (i.e. polynomial time) to solve either side of the problem, but seems to be very hard to solve both at once. One problem is the notation: usually one writes "equivalent to" with the triple-bar equals and says that both sides of the equation are in the same equivalence class. Here I'm saying that the bits match when one uses the customary "mod" function in your favorite language. a is self-inverse for fixed p: x == a(a(x,p),p) One can rewrite the above problem as: Find x != 1,n such that x == a(a(x,p),q). -- Mike Stay staym(a)clear.net.nz

1 1

[math-fun] Most efficient cone puzzle
by asimovd＠aol.com 24 Dec '02

24 Dec '02

For an open cone (ice cream cone shape) of fixed area, find the proportions (ratio of its height to the radius of its base) giving it the maximum volume. --Dan

1 0

[math-fun] Integers with many 0s in base 2 and base 3 (fwd)
by Helger Lipmaa 23 Dec '02

23 Dec '02

---------- Forwarded message ---------- Date: Sat, 21 Dec 2002 00:01:59 -0500 From: Andreas Weingartner <weingartner(a)suu.edu> To: NMBRTHRY(a)LISTSERV.NODAK.EDU Subject: Integers with many 0s in base 2 and base 3 Hello everybody: Here is a problem that comes up in quantum computation. I would appreciate any information on this problem. Prove or disprove: There exists an epsilon>0, such that no natural number has the property that in base 2 as well as in base 3, at most (epsilon)*100% of the digits are nonzero. Example: 513=(1000000001) in base 2 and 513=(201000) in base 3 so epsilon<1/3. Andreas

4 3

[math-fun] Bob Lord's 100 prisoners
by Thane Plambeck 23 Dec '02

23 Dec '02

Here is a puzzle I learned about from Bob Lord, a software entrepeneur and puzzle fan who was grievously injured in a 30-foot accidental fall down an abandoned mineshaft outside Jean, Nevada on 27 October 2002. I have a solution but have no idea if it is the best possible. ***** There are 100 prisoners who will be placed into 100 individual jail cells. There is no way for the prisoners to communicate, once inside. Each day, a guard will choose one prisoner, at random, to enter a special room. In this room, there is a light that the prisoner may turn on or off and that will remain as the prisoner left it until the next prisoner enters, the next day. A prisoner may tell the guard that all of the prisoners have been in this room at least once. If he is correct, they will be released. If he is not correct, they will all be killed. The prisoners are allowed to communicate only before they're all locked up. How will the prisoners cooperate to guarantee their release before they all die of old age? The number 100 is not significant. There is no trickery involved; the puzzle revolves entirely around the state of the light switch. Indeed, the light itself is not significant, as long as they can tell whether the switch is in the on or off position. ***** Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

1 0

Re: [math-fun] Integers with many 0s in base 2 and base 3 (fwd)
by asimovd＠aol.com 23 Dec '02

23 Dec '02

This question remindes me of the news item that's been posted on the homepage of Eric Weisstein's MathWorld for a number of months: << A paper submitted by P. Mihailescu on April 18 [2002] allegedly proves Catalan's 158-year-old conjecture. >> Am I right that this is the conjecture that the only positive integral powers of 2 and 3 that differ by 1 are 3 - 2 = 1 and 9 - 8 = 1 ??? Does anyone know whether this proof has been accepted by experts? If so, can someone please give a sketch of the proof? Thanks, Dan

3 2

[math-fun] hard problem
by Mike Stay 22 Dec '02

22 Dec '02

I was fooling around with dicrete log and came up with the following: Pick p_0, p_1 > n s.t. g is a generator and discrete log is easy for both. Let lg_j be discrete log base g over p_j. Find x s.t. g^{lg_0(n) - lg_0(x)} mod p_0 = g^{lg_1(n) - lg_1(x)} mod p_1 This is a hard problem, since it's equivalent to factoring. I think what I mean is obvious by the notation, but it doesn't really work, since we're dealing with equivalence classes that aren't equal. Is there a better way of writing that? -- Mike Stay staym(a)clear.net.nz

1 0

[math-fun] Re: a(n) = smallest prime >a(n-1) such that sum of first n terms is Fib no.
by Richard Guy 22 Dec '02

22 Dec '02

I think that I have upped this to 10^64, and someone who knew how to sieve could probably go much further. It's a probably fruitless task, but one admits to being tantalized by u_n - u_37 = 919p for n = 144 5p 234 79p 264 9349p 306 Of course, those pees are industrial strength, but there's no doubt that the small factors are OK. R. On Fri, 20 Dec 2002, Neil Fernandez wrote: > 2,3,29,199,2351,24155233, next term >10^15 > > a(n) = smallest prime > a(n-1) such that sum of first n terms is a > Fibonacci number > > a(7), if it exists, > 10^15 > > Neil > -- > Neil Fernandez >

2 1

[math-fun] The next total solar eclipse...
by Thane Plambeck 21 Dec '02

21 Dec '02

...will be in Antarctica, apparently. At least it's the summer season. The hotels are probably already booked. http://sunearth.gsfc.nasa.gov/eclipse/SEplot/SEplot2001/SE2003Nov23T.gif Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/home.htm

1 0

Re: [math-fun] Integers with many 0s in base 2 and base 3 (fwd)
by asimovd＠aol.com 21 Dec '02

21 Dec '02

Andreas Weingartner <weingartner(a)suu.edu> asks: << Prove or disprove: There exists an epsilon > 0, such that no natural number has the property that in base 2 as well as in base 3, [a fraction of at most epsilon] of the digits are nonzero. >> I hereby conjecture that for any epsilon > 0 there is some 2^K and some 3^L such that either of them, expressed in either base 2 or base 3, has a fraction < delta of digits that are nonzero. [My intuition for this is partly based on the yet unproven -- but strongly supported by numerical evidence -- conjecture that the fractional parts of (3/2)^n, n = 1,2,3,..., are uniformly distributed in [0,1).] --Dan

2 1

Re: [math-fun] Integers with many 0s in base 2 and base 3 (fwd)
by asimovd＠aol.com 21 Dec '02

21 Dec '02

This paragraph should have read: I hereby conjecture that for any epsilon > 0 there is some 2^K and some 3^L such that either of them, expressed in either base 2 or base 3, has a fraction <= epsilon of digits that are nonzero. --Dan

1 0