July 2006 - mathfun@mailman.xmission.com

Re: [math-fun] Prime "number system" ? (Goldbach, etc.)
by Michael Reid 10 Jul '06

10 Jul '06

> In an analogy with Zeckendorf (Fibonacci) number systems, > can every positive integer be expressed as a _sum_ of _distinct_ (positive) primes ? > > If not, what is the smallest integer not so expressible? > > For this purpose, I'll allow "1" as a "prime", although I suspect it's only needed a > constant number of times. yes, with your convention of considering 1 to be prime. you've already shown how to do the first few cases. for a larger value of N , let p be the largest prime <= N . then p > N/2 , by the theorem usually called "Bertrand's postulate". express N - p as a sum of distinct "primes", and add p to the result. since p > N - p , the primes in this sum are distinct. it is probably easy to modify this argument to show that 1 is only needed a few times (twice?) mike

2 1

[math-fun] Prime "number system" ? (Goldbach, etc.)
by Henry Baker 10 Jul '06

10 Jul '06

(I hope I am not embarrassing myself with this one...) In an analogy with Zeckendorf (Fibonacci) number systems, can every positive integer be expressed as a _sum_ of _distinct_ (positive) primes ? If not, what is the smallest integer not so expressible? For this purpose, I'll allow "1" as a "prime", although I suspect it's only needed a constant number of times. 2=2 3=3 4=3+1 5=5 6=5+1 7=7 8=5+3 9=7+2 10=7+3 11=11 12=7+5 13=13 14=11+3 15=13+2 16=13+3 17=17 18=13+5 19=19 20=17+3 21=19+2 22=19+3 23=23 24=19+5 25=23+2 26=23+3 27=19+5+3 28=23+5 29=29 etc. I'm not (yet) worried about the smallest number of such primes in the "representation".

1 0

Re: [math-fun] sqrt( |Rubik| ), Google, and humans
by The Purple Streak, Hilarie Orman 10 Jul '06

10 Jul '06

There are about 6x10^9 human brains spread in at least 25 locations around the world, though not in a tight enough cluster. Hilarie

1 0

[math-fun] diameter of Rubik's cube puzzle
by Schroeppel, Richard 10 Jul '06

10 Jul '06

Has the diameter of the Rubik's cube puzzle been established yet? We now have enough computing power to find & prove the distance- to-start for any particular position, using the obvious square-root meet-in-the-middle algorithm and a big disk. We can search for edge positions by generating random positions and using the exact distance algorithm to guide a hill-climb away from the start position. But this is only heuristic. Rich

4 3

Re: [math-fun] 3-dimensional rhombus
by dasimov＠earthlink.net 10 Jul '06

10 Jul '06

Michael Kleber wrote: << Russ Cox wrote: > complete the analogy: > > square : rhombus :: cube : ____ ? Do you mean to require that the twelve edges all have the same length, or that the six faces all have the same area? Or both? Or perhaps you want all faces to be congruent? Now I'm not even sure which Gareth's "equilateral parallelepiped" would best fit -- either the first or the last, I think. >> Technically there are several ways to generalize the rhombus to 3D. But the most natural and symmetric way seems to me for it to be a parallepiped all of whose edges are the same length <=> all of whose faces are rhombi <=> all of whose faces are congruent rhombi. The word for this 3D object is "rhombohedron". (It generalizes neatly to n dimensions. Not sure if there is a word for the n-dimensional object, but perhaps it ought to be "rhombotope".) All such rhombotopes can be obtained from a cube by applying an arbitrary dilatation to one main diagonal while keeping its orthogonal directions fixed, I ween. --Dan

3 3

[math-fun] Stirling's second
by wouter meeussen 10 Jul '06

10 Jul '06

S(n,k)=S(n-1,k-1)+k*S(n-1,k) is a well-known recursion, and I tried to find out which of the two terms dominate. So, I looked for the values n & k where S(n-1,k-1)<=k*S(n-1,k). Going down diagonals in the triangular table of S(n,k) using Table[k = 1; While[StirlingS2[n - 1 + k, k] <= (1 + k)*StirlingS2[n - 1 + k, k + 1] && k < 1000, k++]; k, {n, 256}] and I got: {1, 3, 5, 8, 10, 13, 15, 18, 21, 23, 26, 28, 31, 33, 36, 39, 41, 44, 46, 49, 52, 54, 57, 59, 62, 65, 67, 70, 72, 75, 77, 80, 83, 85, 88, 90, 93, 96, 98, 101, 103, 106, 109, 111, 114, 116, 119, 122, 124, 127, 129, 132, 134, 137, 140, 142, 145, 147, 150, 153, 155, 158, 160, 163, ... The first differences are 2 (106 times) or 3 (149 times). No regularity in sight. Picking out the positions of the 2's, I got: {1, 2, 4, 6, 9, 11, 13, 16, 18, 21, 23, 26, 28, 30, 33, 35, 38, 40, 43, 45, \ 48, 50, 52, 55, 57, 60, 62, 65, 67, 69, 72, 74, 77, 79, 82, 84, 86, 89, 91, \ 94, 96, 99, 101, 103, 106, 108, 111, 113, 116, 118, 120, 123, 125, 128, 130, \ 133, 135, 137,... Again taking first differences, {1, 2, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, \ 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, \ 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, \ 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 2, 2, 3, 2, \ 3, 2} with the 3's at positions {4, 7, 9, 11, 14, 16, 18, 20, 23, 25, 27, 30, 32, 34, 37, 39, 41, 44, 46, 48, \ 51, 53, 55, 58, 60, 62, 65, 67, 69, 71, 74, 76, 78, 81, 83, 85, 88, 90, 92, \ 95, 97, 99, 102, 104} This seems convoluted beyond avail. Why? Wouter.

1 0

[math-fun] Rubik cube 'game graph'
by Guy Haworth 10 Jul '06

10 Jul '06

The Rubik cube is an example of both a 1-person game, and a game for which all positions can be enumerated. The number of moves taken to restore a cube to its 'home position' could be called the 'depth' of that position, analogous with nomenclature in Awari, Checkers and Chess. There can be more than one metric: in chess, more than one goal can be identified - mate, mate and/or conversion of force, mate, mate and/or conversion of force, mate and/or conversion of force and/or Pawn-push. Thus, the metric defines the graph and the depth. The key is to define an indexing of the positions, i.e., a 1-1 into mapping of {positions} --> Z, preferably [0, N] with N as small as possible. The indexing method should be usable to get the index or to derive the position of the cube from the index. Still, I would have thought that 'N' is still challenging for today's computers. 7-man chess endgames, involving an N of about 60^7 are on the limit at the moment. G

1 0

Re: [math-fun] 3-dimensional rhombus
by dasimov＠earthlink.net 10 Jul '06

10 Jul '06

Minor comment: It's not really the "Drexel" anything; rather, Drexel has in recent years provided a web-based newsreader for the much older Usenet newsgroup sci.math.research . There are a number of choices for how you can read the newsgroups, but Drexel's operation of """its""" Math Forum has been riddled with incompetence. I recommend using Google Groups for Usenet and sci.math.research in particular. For one thing, you can read *all*, not just some, of the posts there. For another, if someone cancels their erroneous post for any reason, the cancellation is reflected in Google Groups -- but not in """Drexel's""" math forum (which once had about a one-month outage when they screwed up a new software/hardware rollout). << This thing turns up in 3-D analogues of the Penrose tiling, see e.g. the Drexel Math Forum discussion by Joshua Socolar at . . . . . . >> --Dan

3 2

Re: [math-fun] diameter of Rubik's cube puzzle
by Michael Reid 10 Jul '06

10 Jul '06

> > Has the diameter of the Rubik's cube puzzle been established yet? > ... > > Later a number of variations on the original 3x3x3 puzzle appeared, > including 4x4x4, 5x5x5, and 2x2x2. It must be quite easy to find the > diameter of the last example --- does anybody know what it is? for the 4x4x4 and larger puzzles, the graph is not vertex transitive, at least not in a natural way. this is because the set of positions is naturally identified with a coset space, H \ G , with a right action of G , the group of (legally obtainable) permutations of the cubies. this of course is true for the 2x2x2 and 3x3x3 cubes, but in those cases, the subgroup H of permutations that preserve the solved state is a normal subgroup of G , so it is safe to identify the set of positions with a group, namely H \ G . this means that there is a difference between asking for the diameter of the graph, which is max d(v, w) , the maximum being over all pairs of vertices (v, w) , and asking for the maximal possible distance from the solved state, which is max d(v_0, v_1) , over all possible vertices v_1 , where v_0 is the vertex for the solved position. mike

1 0

[math-fun] 3-dimensional rhombus
by Russ Cox 10 Jul '06

10 Jul '06

complete the analogy: square : rhombus :: cube : ____ ? is there a word for such a thing? russ

4 3