Mathematics desk
< October 29	<< Sep \| October \| Nov >>	October 31 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 30

Divisor of a Mersenne prime

Resolved

Given a Mersenne prime $M_{q}=2^{q}-1$ , empirically I've tested $q|M_{q}-1$ for all 47 known Mersenne primes. Is this a general property? The converse isn't true--that is, if $n|M_{n}-1$ , $M_{n}$ isn't necessarily a Mersenne prime. The first counterexample is $2^{341}-2$ , which is divisible by 11 and 31, so by 11*31 = 341. I haven't been able to make much progress and it seems like this would have been studied before. 67.158.43.41 (talk) 05:13, 30 October 2010 (UTC)[reply]

M_{q}-1=2^{q}-2=2(2^{q-1}-1)

. Therefore, if q is odd, then

q|M_{q}-1

if

q|2^{q-1}-1

. But Fermat's little theorem says that if q is an odd prime then

q|2^{q-1}-1

. This explains why

q|M_{q}-1

for all Mersenne primes (note that q must be prime if M_q is a Mersenne prime). However, as you observe, the converse if not true - there are composite numbers called pseudoprimes to base 2 (also known as a Poulet numbers) which also satisfy

q|2^{q-1}-1

, and hence

q|2^{q}-2

. The smallest Poulet numbers are 341, 561 and 645. Gandalf61 (talk) 09:28, 30 October 2010 (UTC)[reply]

Ah of course, how simple. Thanks for the name for Poulet numbers! 67.158.43.41 (talk) 11:18, 30 October 2010 (UTC)[reply]

The mathematical spontaneity of coffee stirrers

Is this http://i56.tinypic.com/2urqjpj.png the only arrangement of four straight lines that allows each line to cross all the other lines without any triple or quadruple crossing points? And if it is, how can I prove it? —Preceding unsigned comment added by 89.243.205.241 (talk) 20:51, 30 October 2010 (UTC)[reply]

I don't know but here's a math joke: Why do we stir coffee? Answer: To make it sweet! All right, wise guy, then why do we put in sugar first? So that when it dissolves we know we can stop stirring! 84.153.183.246 (talk) 21:00, 30 October 2010 (UTC)[reply]

To prove anything about this I think you need to make the question a bit more precise. What makes two arrangements the same? I think I understand what you're asking and I'm pretty sure the answer is "yes", but I'm not so sure about how to state it in a precise way. Maybe someone else can help with that. Rckrone (talk) 22:43, 30 October 2010 (UTC)[reply]

I do not have much maths education, but I'll try. First off I'll say the colours in the picture don't mean anything. Secondly, an arrangement would be the same as another one if it was a rotation, a reflection (although obviously in this case my current arrangement has reflectional symmetry) or if it just had the crossover points shifted along the lines without the order of crossover points on any of the lines actually changing. 89.243.205.241 (talk) 23:02, 30 October 2010 (UTC)[reply]

Here's a sketch of an argument: the first 3 stirrers form a triangle. The fourth stirrer (call it A) can cross each of first 3 either within the segment that forms a side of the triangle, or outside of it. If stirrer A crosses into the triangle, it has to later cross back out. So then it must cross the triangle an even number of times (which means 0 or twice). If it crosses the triangle zero times, then choose the first and last stirrer it crosses and call these B and C, with the remaining one being D. Stirrers A,B,C form their own triangle, and stirrer D crosses stirrer A between A's intersection with B and C, so D crosses the triangle formed by A,B,C and therefore must cross it twice. So the only possible arrangement is for one of the stirrers to cross the triangle formed by the other 3 exactly twice, and the remaining crossing is outside the triangle. You would then need to verify that all the ways for that to happen look essentially the same. Rckrone (talk) 23:59, 30 October 2010 (UTC)[reply]

For showing all combinations are "essentially the same" it could be much prettier to take one line as the x axis and the other line as the y axis. Formally, this can be justified by use of a linear transformation. The quadrilateral also seems to form in the quadrant containing the intersection of the remaining two lines (where I'm assuming no line is parallel or equal to any other). A proof by cases on the number of intersections with each ray +x, -x, +y, and -y seems relatively brief. Mirror and rotational symmetry cut the number of cases down very far.

Somewhat informally, I think you're trying to show than any 4 nondegenerate (non-parallel and unequal; no triple or quadruple intersections) lines enclose exactly 1 trapezoid and 2 triangles, all other regions being unbounded. The trapezoid shares exactly 1 side with each triangle, the triangles share no sides, and all three shapes share exactly one vertex.

A higher level but more difficult argument would be to show that the four lines x=0, y=0, y=1-x, and y=3-2x can be continuously deformed into any nondegenerate arrangement of 4 lines, where the topology given by the regions formed and their adjacencies is unaltered by any continuous deformation, i.e. is a topological property. I've studied very little topology, but I'd suspect many of the tools for this proof are well-known to those who have studied it more. 67.158.43.41 (talk) 11:40, 31 October 2010 (UTC)[reply]

Algorithm for next term in series

A while back, my teacher showed the class a way to construct a polynomial function that could satisfy any series (example, for a series like -2, 4, 8, -2.3, and 0, this algorithm would produce a function f(n) such that f(1) = -2, f(2) = 4, etc). I forget how it worked though, although I remember it has something to do with subtracting each term by the one next to it, and continuing this until they're all zero. 76.68.247.201 (talk) 22:06, 30 October 2010 (UTC)[reply]

That's one way of doing it. Another is given in Lagrange polynomial. Algebraist 22:22, 30 October 2010 (UTC)[reply]

What you're remembering is maybe Newton's forward difference formula. You can also do it by solving a system of linear equations; see [1], for example. —Bkell (talk) 23:52, 30 October 2010 (UTC)[reply]

Thanks! 76.68.247.201 (talk) 03:46, 31 October 2010 (UTC)[reply]

The J formula is etc=.({.[:{."1(2-/\])^:([:i.#))^:2 and the test run 20 etc _2 4 8 _2.3 0 produces _2 4 8 _2.3 0 81 346 939.5 2045.2 3886 6724 10860.5 16636 24430.2 34662 47789.5 64310 84760 109715.2 139790.5 Bo Jacoby (talk) 07:29, 31 October 2010 (UTC).[reply]

Would you mind verbally explaining that syntactic magic? Just curious. (I know I could look it up, but it seems way more efficient for someone knowledgeable to just say what it means.) 67.158.43.41 (talk) 11:41, 31 October 2010 (UTC)[reply]

Sure! Here are some commented intermediate results.

  n=._2 4 8 _2.3 0 NB. input
  D=.2-/\] NB. computing Differences (-) between pairs (2)
  D n NB. once
_6 _4 10.3 _2.3
  D D n NB. twice
_2 _14.3 12.6
  D^:3 n NB. three times
12.3 _26.9
  D^:0 1 2 3 4 n NB. table of differences
  _2     4    8 _2.3 0
  _6    _4 10.3 _2.3 0
  _2 _14.3 12.6    0 0
12.3 _26.9    0    0 0
39.2     0    0    0 0
  T=.[:{."1 D^:([:i.#)NB. first ({.) column ("1) is the Transform 
  T n NB. Transform of input
_2 _6 _2 12.3 39.2
  10 {. T n NB. extend the Transform with zeroes
_2 _6 _2 12.3 39.2 0 0 0 0 0
  T 10 {. T n NB. Retransform to obtain the extended input
_2 4 8 _2.3 0 81 346 939.5 2045.2 3886
  etc =.({. T)^:2 NB. define the function
  10 etc n NB. see it work
_2 4 8 _2.3 0 81 346 939.5 2045.2 3886
  etc f. NB. express the function without using intermediate functions T and D.
({. ([: {."1 (2 -/\ ])^:([: i. #)))^:2

You may download from www.jsoftware.com and play with it yourself. Have fun! Bo Jacoby (talk) 08:06, 1 November 2010 (UTC).[reply]

Thank you! I enjoy functional programming conceptually, and this extreme version of it is quite interesting. I had trouble figuring out precisely what the transform was doing, and the rules of currying and uncurrying are unclear to me. But still, I had fun going through the first half or so of the tutorial; maybe I'll finish it someday :). 67.158.43.41 (talk) 22:21, 5 November 2010 (UTC)[reply]