May 2008 - mathfun@mailman.xmission.com

[math-fun] NP super-problems
by rcs＠xmission.com 25 May '08

25 May '08

We could solve NP problems if we had an efficient way to calculate either a) F(N,D) = sum(1<=n<=N, 1<=d<=D) floor[n/d] or b) G(N,D) = sum(1<=n<=N) #{ divisors d of N such that 1<=d<=D } "Efficient" means polynomial in the logs of N and D. It's not obvious to me that we could solve these problems even with an NP (or #P) oracle, so perhaps they are stronger than NP. Rich

2 2

Re: [math-fun] Prefactored large numbers
by Henry Baker 24 May '08

24 May '08

n! n^n Could you be a little more specific about the types of numbers and/or factors you're looking for? At 10:16 AM 5/24/2008, Dan Asimov wrote: >Can anyone please tell me if there's a source of prefactored large numbers >(the larger the better) on the web? > >I'm looking for trends, so artificially manufactured numbers like the RSA-n's would not be of interest. > >Ideally, they would be in a consecutive range, like >{10^50 + K : 1 <= K <= 10^7}, for instance. > >Thanks, > >Dan

1 0

[math-fun] Prefactored large numbers
by Dan Asimov 24 May '08

24 May '08

Can anyone please tell me if there's a source of prefactored large numbers (the larger the better) on the web? I'm looking for trends, so artificially manufactured numbers like the RSA-n's would not be of interest. Ideally, they would be in a consecutive range, like {10^50 + K : 1 <= K <= 10^7}, for instance. Thanks, Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] First known AP25
by Christian Boyer 22 May '08

22 May '08

New longest known arithmetic progression of primes! Here is the first known AP25, found 2 days ago: 6171054912832631 + 366384*23#*n, for n=0 to 24 (Raanan Chermoni & Jaroslaw Wroblewski, May 17 2008) With such an AP, we can directly get a 5x5 pandiagonal magic square of primes. Pandiagonal means that the broken diagonals are also magic, here 20 different lines having the same sum 35759534049087955: 6171054912832631 6743218519407191 7315382125981751 7478857442145911 8051021048720471 7070169151735511 7642332758310071 7805808074474231 6334530228996791 6906693835571351 7969283390638391 6498005545160951 6661480861325111 7233644467899671 7397119784063831 6824956177489271 6988431493653431 7560595100227991 8132758706802551 6252792570914711 7724070416392151 7887545732556311 6416267887078871 6579743203243031 7151906809817591 6171054912832631 6171054912832631 6171054912832631 6171054912832631 6171054912832631 This square should have the biggest magic sum of any known magic square of primes, for ANY order >= 5. On the orders 3 and 4, we can construct magic squares of primes having bigger magic sums, using the Oakes's AP9 and Anderson-Lee's AP16 http://en.wikipedia.org/wiki/Primes_in_arithmetic_progression Christian.

1 1

Re: [math-fun] Smallest term in Zeckendorf representation
by N. J. A. Sloane 20 May '08

20 May '08

Steve Witham said: In OEIS terms, is this sequence interesting? I guess "nonn" and "easy". Is it "nice"? Name(?): Smallest term in Zeckendorf representation of n http://en.wikipedia.org/wiki/Zeckendorf's_theorem 1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, 13, 1, 2, 3, 1, 5, 1, 2... Me: i agree it is nice. It will be A139764 in the OEIS in a few minutes I would not normally post this kind of message to the full mailing list, but my first (direct) message to you seems to have bounced. Best regards Neil

1 0

[math-fun] q^n mod p^n
by Dan Asimov 20 May '08

20 May '08

For primes q > p, the sequence q^n mod p^n, n = 1,2,3,... seems mysterious. E..g, 2^n mod 3^n is: 1, 1, 3, 1, 19, 25, 11, 161, [next 25 or so terms continue to increase],... [tip o' the hat to OEIS A002380: http://www.research.att.com/~njas/sequences/A002380 ] 5^n mod 2^n is: 1, 1, 5, 1, 21, 9, 45, 225, 225, 357, 761, 1757, 2641,... 5^n mod 3^n is: 2, 7, 17, 58, 209, 316, 5180, 3526, 4508, 22540, 112700, 209206,... All of these (based on only a few terms) appear to be eventually monotonic; 5^n mod 3^n appears to be monotonic, period. Is anything known about this phenomenon? --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

3 2

[math-fun] Correction to q^n mod p^n
by Dan Asimov 19 May '08

19 May '08

Correction: Of course, that first sequence is not 2^n mod 3^n. It is 3^n mod 2^n. _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

[math-fun] Gas Pump Mechanical Computers
by Steve Witham 19 May '08

19 May '08

Gas stations with old fuel pumps with mechanical meters are worried because they don't go above $3.999/gal without an expensive retrofit. http://www.usatoday.com/money/industries/energy/2008-05-17-old-gas-pumps_N.… It occurred to me that those things are mechanical multipliers with four-digit accuracy. How do they work? In the trade the part that does that is called the "computer" or "mechanical computer". At the page above you see a glimpse of one. PMP Corp., mentioned in the article, sells Veeder-Root meters. VR's pages about them have interesting jargon: http://www.veeder.com/page/VR104Pump http://www.veeder.com/page/VR10Pump This FAQ page has links to various PDFs with photos and diaagrams: http://www.pmp-corp.com/FAQs.asp?FAQMID=3&NumFaq=10&bmode=Main They also have things called "non-computers"! I think they just measure volume & don't multiply out the price. Funny that these and the Babbage machine have been in the news so close together. --Steve

1 0

Re: [math-fun] Smallest term in Zeckendorf representation
by Dan Asimov 18 May '08

18 May '08

<< What you presumably are interested in is a continuous extension whichs in some way "natural", as in factorial vis-a-vis Gamma function. > Does the Fibonacci multiplication (which Knuth > denotes with just a circle: x o y) have a > continuous extension to the positive reals > that remains commutative and associative ? >> A natural extension would be nice, but for now I'm interested in a continuous extension to the positive reals that remains commutative and associative. --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

Re: [math-fun] Smallest term in Zeckendorf representation
by Dan Asimov 18 May '08

18 May '08

Here's a question that probably has an obvious answer, but I have to ask it: Does the Fibonacci multiplication (which Knuth denotes with just a circle: x o y) have a continuous extension to the positive reals that remains commutative and associative ? --Dan P.S. All definitions are here: http://en.wikipedia.org/wiki/Zeckendorf's_theorem _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1