September 2005 - mathfun@mailman.xmission.com

Re: [math-fun] Array with primes
by Eric Angelini 07 Sep '05

07 Sep '05

"Michael B Greenwald" > Actually, I think the def'n is the same as A105441, > not A093642. ... 55 doesn't belong to "our" array -- but is in A105441. Best, É.

2 1

[math-fun] Array with primes
by Eric Angelini 07 Sep '05

07 Sep '05

Hello SeqFan, consider this array where the 1st column is made of all prime numbers, and the nth term of a row is 2 times the previous one on the same row [P(n)=P*2^n]: p px2 px4 px8 px16 px32 px64 px128 px256 px512 2 4 8 16 32 64 128 256 512 1024 ... 3 6 12 24 48 96 192 384 768 1536 ... 5 10 20 40 80 160 320 640 1280 2560 ... 7 14 28 56 112 224 448 896 1792 3584 ... 11 22 44 88 176 352 704 1408 2816 5632 ... 13 26 52 104 208 416 832 1664 3328 6656 ... 17 34 68 136 272 544 1088 2176 4352 8704 ... 19 38 76 152 304 608 1216 2432 4864 9728 ... 23 46 92 184 368 736 1472 2944 5888 11776 ... 29 58 116 232 464 928 1856 3712 7424 14848 ... 31 62 124 248 496 992 1984 3968 7936 15872 ... 37 74 148 296 592 1184 2368 4736 9472 18944 ... 41 82 164 328 656 1312 2624 5248 10496 20992 ... 43 86 172 344 688 1376 2752 5504 11008 22016 ... 47 94 188 376 752 1504 3008 6016 12032 24064 ... 53 106 212 424 848 1696 3392 6784 13568 27136 ... .. ... ... ... 1) The missing integers in this array are : 1 9 15 18 21 25 27 30 33 35 36 39 42 45 ... ...which (except the first term 1) are A093642. 2) The main diagonal (NW-SE) reads: 2 6 20 56 176 416 1088 2432 5888 14848 ... ...which is not in the OEIS 3) Other diagonals (NE-SW) sum up to: 2 = 2 (4+3) = 7 (8+6+5) = 19 (16+12+10+7) = 45 (38+24+20+14+11) = 101 (64+48+40+28+22+13) = 215 ... this is not in the OEIS . 4) If one keeps only the "primitive terms" of A093642 one gets: A093642 : 1 9 15 18 21 25 27 30 33 35 36 39 42 45 49 50 "primitives": 1 9 15 .. 21 25 .. .. 33 35 .. 39 .. .. 49 .. ... and again, this is not in the OEIS : 1 9 15 21 25 33 35 39 49 ... If this is of interest, could someone kindly check, compute more terms and enter those sequences in the OEIS? Best, Angelini & Wajnberg

2 1

[math-fun] Rosser provability
by Thomas Colthurst 06 Sep '05

06 Sep '05

S is a Rosser proof of the formula A iff S is a proof of A and all proofs S' with smaller Godel code than S don't prove not(A). The great thing about Rosser provability is that it is consistent: you can prove in 1st order Peano arithmetic that for all x, x isn't the Godel code of a Rosser proof of 0=1. The not so great thing about Rosser provability is that it can be a bit, well, slow to check if S is a Rosser proof of A. This leads me to my first question: (1) Given a length n proof of A, what's the computational complexity of checking that it is a Rosser proof? Naively, it's something like O( n 2^n ), but surely you can do a bit better? My second question is probably conclusive evidence that the whole field of logic is just too darn subtle for me: (2) Is there a normal provabile but not Rosser provabile formula A? If so, why doesn't this imply the existence of a proof of not(A) [aka the inconsistency of PA] ? If not, why doesn't this prove the consistency of normal provability? -Thomas C

1 0

[math-fun] Sudoku, minimal number of clues
by Gary McGuire 06 Sep '05

06 Sep '05

I have been spending way too much time on sudoku. There are a few interesting questions around, but most have been solved. There is one remaining big open question: What is the fewest number of clues a sudoku can have? The current record is 17. Here is an example of a puzzle with 17 clues. . 9 8 . . . . . . . . . . 7 . . . . . . . . 1 5 . . . -------+-------+------- 1 . . . . . . . . . . . 2 . . . . 9 . . . 9 . 6 . 8 2 -------+-------+------- . . . . . . . 3 . 5 . 1 . . . . . . . . . 4 . . . 2 . (It is convention that a sudoku puzzle has a unique solution. If there are multiple solutions then the puzzle is not valid. An embarrassing such puzzle was carved into a hillside in England by Sky TV to promote their new sudoku tv show. See http://www.sudoku.org.uk/blunder.htm Also the 3rd puzzle printed by the Daily Telegraph had multiple solutions. Their setter had only just learned the puzzle and hadn't perfected his program yet.) Say you want to construct a sudoku with 16 clues. (This has been discussed on lots of internet chat sites.) Start with a given completed sudoku grid. Then you might look for sets like the following: 1 2 . ... ... . . . ... ... . . . ... ... 2 . 1 ... ... . . . ... ... . . . ... ... . 1 2 ... ... . . . ... ... . . . ... ... It's clear that 1 and 2 can be interchanged IN THESE 6 CELLS ONLY and we still have a valid completed grid. Conclusion: in any sudoku puzzle with this completed grid as the answer, one of these 6 numbers must be a clue. Call a set like this an unavoidable set, or a fated set, or something. The size of a fated set can vary, there are some obvious ones with 4 elements: 12. ... ... ... ... ... ... ... ... 21. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... Of course not every grid has an unavoidable set like this one. If a set of clues does not intersect every fated set, it cannot be used as a set of clues for a sudoku puzzle. So, for a given grid, we want all its fated sets and then we want to search for a set of size 16 that intersects all the fated sets. If we find one, we may also need to check that the puzzle is solvable from these clues, I'm not sure about this bit. Clearly we would like to choose the grid so that it has relatively few fated sets. What types of grids have this property? Are there clever ways to search for the set of size 16? Is this approach feasible? This may be related to the automorphism groups of sudokus, and also to the matrix arising from the dancing links method. I will post a bit about these in other messages. This is already too long. Gary McGuire

4 3

[math-fun] Describe and add
by Eric Angelini 06 Sep '05

06 Sep '05

Could please someone compute and analyse this sequence? Start with a(1) = 1 Describe a(1) --> = 11 (one "1") Add a(1) to it's description: 1 + 11 = 12 This is a(2) -- so we have: a(1) = 1 a(2) = 12 Go on from there : Description of a(2) : 1112 Add a(2) to it's description: 12 + 1112 = 1124 This is a(3) -- we have now: a(1) = 1 a(2) = 12 a(3) = 1124 Go on from there : Description of a(3) : 211214 Add a(3) to it's description: 1124 + 211214 = 212338 This is a(4) -- we have now: a(1) = 1 a(2) = 12 a(3) = 1124 a(4) = 212338 Go on from there : Description of a(4) : 11222318 Add a(4) to it's description: 212338 + 11222318 = 11434656 This is a(5) -- we have now: a(1) = 1 a(2) = 12 a(3) = 1124 a(4) = 212338 a(5) = 11434656 etc. -------- Questions: - has this seq. a fixed point (or loop)? - what about other beginnings? (start with a(1) = 0 for instance) Best, É.

3 5

[math-fun] Re: Describe and add
by Eric Angelini 06 Sep '05

06 Sep '05

Hello to all, back from the Lido, [Hugo]: > Check Eric's original series of examples again: > this is not Conway's "look and say" type of des- > cription. My guess (as encoded in my perl) was > that the digits are sorted before describing, > so that the description of 212338 is 11222318. ... yes, indeed -- this is exactly it -- bravo Hugo, and apologizes for not beeing clear enough (happens to me far too often, I admit) Could I kindly ask to Hugo to express in good english and mathematical terms how A109229 works -- and add this comment to the OEIS? And, Michele, why wouldn't you submit your (equi- valently sound) sequence to the database? Best to both of you, É.

1 0

[math-fun] more on bijections on partitions
by wouter meeussen 04 Sep '05

04 Sep '05

Odd-Strict partitions <--> Self Conjugate partitions OEIS : A000700 the Ferrer's plots are a dead give-away: start from a self-conjugate partition with its symmetric Ferrer's plot, peel the onion by taking away its first row and column, repeat on the rest until nothing left. The lengths of the peels (obviously different, obviously odd) are the corresponding odd-strict partition. Mma: peel[par:{__Integer}]:=-1+2*Map[First,Drop[FixedPointList[DeleteCases[Rest[#]-1,0|{}]&,par,SameTest- >( #2==={}&)],-1]] joinpeels[rinds:{__Integer}]:=Flatten[{#,Drop[TransposePartition[#],Length[#]]}]&[(1+rinds)/2+Range[ 0,Length[rinds]-1] ] Partitions in more than one part, you *got* to love them. W.

1 0

Re: [math-fun] orbit problem -> segment thickness problem
by R. William Gosper 03 Sep '05

03 Sep '05

hgb>This is very cool! Do you have a reference to an article for amateurs? A couple of years ago, the Car Talk radio show and website featured the puzzle of how to quarter-fill a horizontal cylindrical tank, so a lot of math teachers may have been embarrassed already. Unfortunately, I didn't see their solution, and it's no longer obvious on their site. I also haven't seen the area problem phrased as a "parabolic" (epsilon = 1) case of Kepler's, but it's fairly obvious. An efficient area solution might be useful as the lead term of an expansion at epsilon = 1 of the high eccentricity Kepler case. Watson gives the solution in terms of Bessel functions as a standard Fourier expansion involving a slick integration by parts which turns Kepler's equation into one of the usual definite integral definitions of the Bessel function. I'll send it along if there's any interest. Twice I said >b) although the equation of motion of an elliptical orbit requires higher >transcendental functions,[...] (The hard part is theta(t), which apparently even transcends Lambert_W.) But just barely. t = time ~ M, the "mean anomaly", and the problem is to solve E - eps sin(E) = M for E, the "eccentric anomaly". In a (comfortable) neighborhood of M = 0, Kepler's eqn is (nonobviously) equivalent to | i M - eps cos(E) | |W(- e eps)| = eps. >Also, do the transcendental functions show up for "even" numbers of >dimensions? For dimensions 0..5, thickness x, the volume formula gives sqrt(x) 2 asin(-------) sqrt(2) v(0) = ---------------, v(1) = x, %pi sqrt(x) sqrt(2) asin(-------) (x - 2) (x - 1) sqrt(2) v(2) = - sqrt(2) (--------------- - ---------------------) sqrt(x), x sqrt(x) 2 sqrt(1 - -) 2 x 2 v(3) = %pi (1 - -) x , v(4) = sqrt(2) %pi sqrt(x) 3 sqrt(x) 2 3 sqrt(2) asin(-------) (x - 2) (x - 1) (2 x - 4 x - 3) sqrt(2) (-------------------------------- + -----------------------)/6, x sqrt(x) 2 sqrt(1 - -) 2 x 3 (1 - -) x 2 3 5 2 %pi x (1 - -----------) 4 v(5) = ---------------------------, 3 and the hypergeometric three-term relations give the recurrence v(n) = 2 %pi (2 %pi v(n - 4) (x - 2) x 2 - v(n - 2) ((n - 2) (x - 2 x - 1) - 1))/((n - 1) n), which proves transcendence iff n even. --rwg SELF-DEVOURING GIRDLE-OF-VENUS STREAMLINES RAIMENTLESS ETERNALISMS

1 0