ECE 5530 Homework 4

By Andrew Love

Problem Description:

We wish to use the Lucas-Lehmer Test for to find a Mersenne Prime (The form is 2^p-1) for a small p using a Lego Mindstorms Kit.

Solution Description:

I implemented a gear-based implementation of the Lucas-Lehmer test for p = 3. The Lucas-Lehmer equation is as follows:

s_n = ( s²_n-1 – 2 ) mod Mp, where Mp = 2^p-1. The number is prime if s_p-2 (the Lucas-Lehmer Residue) is 0.

For p = 3, the equations simplify down to s_p-2 = s_3-2 = s₁ = (s₀² – 2) mod 2³-1, s₀ = 4. So the final equation to be implemented using Legos is:

s₁ = (4²-2) mod 2³-1.

In order to implement this without using a computer, multiple gears are needed. Also, an input is necessary to begin the operation. It was decided that the input should be the s₀ value, 4. This input is entered into the Lego machine by rotating an axle through 4 complete revolutions. To implement the 4² operation, two gears with equal gear ratios were used. One of these gears was connected to the input and the second was modified so that it also has 4 larger gear spokes. By rotating a gear with four spokes four times, a total of 16 spoke passes occur from the viewpoint of another gear.

To represent 7, a gear with seven gear spokes was used. The –2 term was included within this gear as well. This is done by emplacing marker Legos on the 7 spoked gear which are of different colors and have a displacement of 2 between them.

The entire device was connected together so that a rotation of the gear with 4 spokes would turn the gear with 7 spokes. Since the gears are round, modular arithmetic can simply be represented as the final position of the gear after the input has been fully entered. The relative scales of the gears can be seen here:

The following photos show the device and then 4 complete rotations of the input axle, which is the axle on the right with the grey L connector on it. The orientation of the L connector is the same in all of the pictures because they are after complete rotations of the axle..

Initial Position

After 1 complete rotation

After 2 complete rotations

After 3 complete rotations

After 4 complete rotations (Final Position)

Note that the Yellow end block is now in the same position as the green block was initially. That signifies that the resulting solution from the p = 3 Lucas-Lehmer test is 0. This means that 2³-1, or 7, is a Mersenne Prime.

Another way to input the rotations is through a motor. The following picture shows the device hooked up to a motor and a controller.

Device with Motor and Controller

Device Utilization:

Device Number Used

Large Gear 1

Medium Gear 3

Small Gear 3

Tiny Gear 2

6x1 ‘Spoke’ 11

Green Start Block 1

Yellow End Block 1

Medium Axle 5

12x1 Holed Block 2

16x1 Holed Block 2

8x1 Holed Block 2

4x1 Holed Block 6

4x1 Thin Block 4

L Connector 1

L Block 1

4x2 Green Block 1

10x2 Thin Block 3

8x2 Green Thin Block 1

6-2 Green Trapezoid 1

Mechanized Additions:

Axle Connector 1

Motor 1

Electrical connector 1

Lego Mindstorms Controller 1

Performance Results:

This device successfully solves the p = 3 case of the Lucas-Lehmer Test, but it is not a scalable solution.

This implementation does have an interesting property. The entire equation is solved while the input is being entered into the system. As soon as the input ‘stream’ completes, the solution is available. However, the process of entering the input takes significant time (in the realm of seconds), so there is no chance of it being competitive with a computational solution, which acts in the µs range.

Possible scalable solutions may need to include some kind of a rotation sensor to interface with the controller. This would allow for an increase in the granularity of the possible gear ratios and s_n values. It would also allow for the solution of the previous part to be used as an input for the number of rotations in the next step.