March 28, 2024, 12:57:15 pm

News:

This site is now on a new server!


A Novel Prime/Factoring Algorithm

Started by Unbeliever, January 17, 2007, 04:03:45 pm

Previous topic - Next topic

Unbeliever

January 17, 2007, 04:03:45 pm Last Edit: January 20, 2007, 01:28:16 pm by Unbeliever
Several years ago, in 1998, I was playing around with knight's tours, putting them on various shaped  objects, such as cubes, tubes, etc., and at some point I decided to link a series of open tours together around the surface of a Moebius band. This got me to thinking about Moebius bands, and having fun with them, and I got to wondering what would happen if, instead of a flat strip of paper, a length of material with a square cross-section was given a half twist before joining the ends. I could see right away that it would form a ring with 2 sides and two edges, not a Moebius ring. It would be equivalent to simply thickening the edge. So I shelved the idea for the time being, but, a couple of days later when I was at work, and bored (I was washing cars at the time), I decided to think about it some more. So I mentally gave the square-shaped length of material a 1/4 twist, instead of a 1/2 twist, and I realized that such an opertion would indeed make a single-sided ring, with only one edge. So I thought about giving it a 3/4 twist, with the same result.

Well, I thought that was kind of interesting, though it didn't seem useful, but then I wondered what a length of material with a triangular (3-sided) cross-section would do, and realized that it didn't matter whether I gave it a 1/3 or a 2/3 twist (the only non-whole number twists available), they both resulted in a single-sided ring.

At first I didn't appreciate the difference between the square cross-sectional ring and the triangular one, but I soon realized the difference: the square one only made a single-sided ring with some twists but not others. The case of the triangular ring made a single-sided ring no matter which fraction (non-whole number) of twists it got.

So I thought about a ring with a five-sided (pentagonal) cross section, and found that it, too, made a single-sided ring no matter which fractional twists it got.

I soon found that a 6-sided ring would, like the 4-sided one, only make a Moebius ring with some twists, but not others.

Since I knew that 2, 3 and 5 were prime, but that 4 and 6 are not, I was now getting a bit excited, thinking I'd stumbled on to something really interesting, but I needed to see what would happen with rings with more sides, but by then it was quitting time. So I went home, and, with paper and pencil, started investigating the connectivity of rings with more than 6 sides. What I discovered was that, if a number (the sides, S) was a prime number, then no matter which fractional twist it got, it formed a single-sided (Moebius) ring, but that composite numbers of sides would form a Moebius ring only with some fractional twists but not others.

I wasn't actually constructing these things, though, as I hadn't the materials to do so. I graphed them by (mentally) numbering each side, at each end, imagining which side would meet which other side given a particualar fractional twist.

The easiest was, of course, the normal Moebius band, and it's trivially simple to see that, given a half twist, side 1 will meet side 2 and side 2 will meet side 1.

I graphed it as follows:


S=2

1/2
_____
1---2
2---1

[note: with pencil and paper I drew a complete loop from 1 in the left column back to the same 1. I can't do that in this format, sorry!]

Notice that 1/2 is the only fractional twist available in this case. And since the only available fractional twist makes a column (hereafter called a Moebius column) that forms a single-sided  ring, this indicates its primality, having no factors other than itself and 1. More on this later - I'll be repeating things a lot, but I feel it's necessary for full understanding.

In all of these graphs, always start at side 1 in the left column for a given fraction, go directly across to whichever number is directly across in that column, then go to that same number in the left of the column, and continue until you get back to the original 1 that you began with. Some graphs, the ones associated with primes, will use every number in the loop, but composite numbers will use only some of the numbers in the loop.

___________________________
A triangular cross-sectional ring graphs like this:

S=3

1/3.........2/3
_____________
1---2......1---3
2---3......2---1
3---1......3---2
[note: the dots are merely for spacing and mean nothing.]

In the case of the 1/3 twist, side 1 meets side 2, side 2 meets side 3, and side 3 meets back at side1, forming a single-sided ring with a continuous loop from 1 back to 1, as in the case of the simple Moebius band.

With a 2/3 twist, side 1 meets side 3, side 3 meets side 2, and side 2 meets back at side 1, again forming a single-sided ring, and a single loop.

Since there are 2 available fractional twists, and they both form Moebius rings, the number 3 is prime.
___________________________
Here is the graph for a 4-sided ring, with the result that only the 1/4 and 3/4 twists will form a Moebius ring, whereas the 2/4 (1/2) twist results in a ring with 2 sides. So 4 is not prime, because not all of the columns are Moebius columns. Notice also in the graphs that any fraction that is reducable to a simpler fraction is associated with a non-Moebius column.

S=4

1/4.........2/4.........3/4
_____________________
1---2......1---3......1---4
2---3......2....4.......2---1
3---4......3---1......3---2
4---1......4....2.......4---3
___________________________
As is the case with 2 and 3, a 5 sided ring forms a single-sided ring given any fractional twist:

S=5

1/5........2/5........3/5........4/5
______________________________
1---2......1---3......1---4......1---5
2---3......2---4......2---5......2---1
3---4......3---5......3---1......3---2
4---5......4---1......4---2......4---3
5---1......5---2......5---3......5---4

Since every column is a Moebius column, the number 5 is prime.

___________________________
A 6 sided ring, like the 4 sided one, gives a Moebius ring only with some fractioanal twists, but not others, and so 6 is not prime.

S=6

1/6........2/6........3/6........4/6........5/6
______________________________________
1---2......1---3......1---4......1---5......1---6
2---3......2....4.......2....5......2....6......2---1
3---4......3---5......3.....6......3---1......3---2
4---5......4....6.......4---1......4....2......4---3
5---6......5---1......5.....2......5---3......5---4
6---1......6....2.......6....3......6....4......6---5

________________________________
The 7-sided ring, again, forms a Moebius ring with any twist, so 7 is prime.

S=7

1/7........2/7........3/7........4/7........5/7........6/7
______________________________________________
1---2......1---3......1---4......1---5......1---6......1---7
2---3......2---4......2---5......2---6......2---7......2---1
3---4......3---5......3---6......3---7......3---1......3---2
4---5......4---6......4---7......4---1......4---2......4---3
5---6......5---7......5---1......5---2......5---3......5---4
6---7......6---1......6---2......6---3......6---4......6---5
7---1......7---2......7---3......7---4......7---5......7---6
_______________________________________
An 8-sided ring forms a Moebius ring only with 1/8,3/8,5/8, and 7/8, but not with 2/8, 4/8, or 6/8. 8 is, therefore, not prime.

S=8

1/8........2/8........3/8........4/8........5/8........6/8........7/8
_______________________________________________________
1---2......1---3......1---4......1---5......1---6......1---7......1---8
2---3......2....4......2---5......2....6......2---7......2....8......2---1
3---4......3---5......3---6......3....7......3---8......3---1......3---2
4---5......4....6......4---7......4....8......4---1......4....2......4---3
5---6......5---7......5---8......5---1......5---2......5---3......5---4
6---7......6....8......6---1......6....2......6---3......6....4......6---5
7---8......7---1......7---2......7....3......7---4......7---5......7---6
8---1......8....2......8---3......8....4......8---5......8....6......8---7

_______________________________________________
A 9-sided ring makes a Moebius ring only with 1/9, 2/9, 4/9, 5/9, 7/9 and 8/9, but not with 3/9 or 6/9. 9 is not prime.

S=9

1/9........2/9........3/9........4/9........5/9........6/9........7/9........8/9
_______________________________________________________________
1---2......1---3......1---4......1---5......1---6......1---7......1---8......1---9
2---3......2---4......2....5......2---6......2---7......2....8......2---9......2---1
3---4......3---5......3....6......3---7......3---8......3....9......3---1......3---2
4---5......4---6......4---7......4---8......4---9......4---1......4---2......4---3
5---6......5---7......5....8......5---9......5---1......5....2......5---3......5---4
6---7......6---8......6....9......6---1......6---2......6....3......6---4......6---5
7---8......7---9......7---1......7---2......7---3......7---4......7---5......7---6
8---9......8---1......8....2......8---3......8---4......8....5......8---6......8---7
9---1......9---2......9....3......9---4......9---5......9....6.......9---7......9---8

______________________________________________________

So far I haven't mentioned the factors of composite numbers, so I'll discuss that now.

If you'll look again at the graph for S=4, you can see that the central column in the graph (2/4) has only 2 horizontal lines connecting the left and right sides of that column. It is the case that 2 separate loops can be made, one starting at the 1 in the left side, and another starting at the 2 in the left side. This means that 2 is a factor of 4, because that column contains 2 loops. In the same way, the graph for S=6 has a column, representing 2/6, that has only 3 lines connecting the two sides of the column, and the column representing 3/6 has only 2 connecting lines. This means that 2 and 3 are factors of six, the only ones.

Similarly, in the graph for S=8, it can be seen that the factors are 2 and 4, and in the graph for S=9, the only factor is 3.

This pattern holds true for any S, as far as I can tell.

A year or so after I first developed the algorith, I found a book, Fractal Music, Hypercards, and More, by Martin Gardiner, in which he discusses these objests, which he called "twisted prismatic rings". That term seemed much better that what I had been using, "3 dimensional Moebius bands", or "polygonal Moebius bands", so I've since been using his term.

Here are some definitions of terms:

S=the number of sides of a twisted prismatic ring; a whole number that represents a regular convex polygon
F=the number of fractional twists between S and S+1
M=the number of Moebius columns in a particualr graph
N=the number of non-Moebius columns in a graph

Here are some relations that hold:

For all S
F=S-1=N+M

For prime S
M=S-1=F=phi(s) (see below)

A couple of years ago, while browsing the math section of the local library, I came across a book, The Penguin Dictionary of Curious and Interesting Numbers, Revised edition, 1997, by David Wells, in which was a table, on pg. 220, The Proper Factors, Where Composite, and the Values of the Functions phi(n), d(n) and sigma(n)
[note: only the section of the table for phi(n) is reproduced below, since it is the only relevant portion]

n.......phi(n)

2.......1
3.......2
4.......2
5.......4
6.......2
7.......6
8.......4
9.......6
10.....4
11.....10
12.....4
13.....12
14.....6
15.....8
16.....8
17.....16
18.....6
19.....18
20.....8
21.....12
22.....10
23.....22
24.....8
25.....20
26.....12
27.....18
28.....12
29.....28
30.....8
31.....30
32.....16
33.....20
34.....16
35.....24
36.....12
37.....36
38.....18
39.....24
40.....16
41.....40
42.....12
43.....42
44.....20
45.....24
46.....22
47.....46
48.....16
49.....42
50.....20
51.....32
52.....24
53.....52
54.....18
55.....40
56.....24
57.....36
58.....28
59.....58
60.....16
61.....60
62.....30
63.....36
64.....32
65.....48
66.....20
67.....66
68.....32
69.....44
70.....24
71.....70
72.....24
73.....72
74.....36
75.....40
76.....36
77.....60
78.....24
79.....78
80.....32
81.....54
82.....40
83.....82
84.....24
85.....64
86.....42
87.....56
88.....40
89.....88
90.....24
91.....72
92.....44
93.....60
94.....46
95.....72
96.....32
97.....96
98.....42
99.....60
100...40

I realized that the list of phi(n) was identical to the list of Moebius fractions in my algorithm, but I'm still not sure if there's any significance to that fact.

Here's a much more extensive list of phi(n), to 999:
http://www.users.globalnet.co.uk/~perry/maths/phi/morephi.htm )


I hope that's enough to get the idea across, since it's fairly tedious to work with larger numbers, and I'll run out of room on the page. I have previously gotten all the way up to 64 on paper, which took some doing, as you can imagine. Since it's easy to find which numbers of this size range are prime, I was able to verify that, for every prime number, 64 or smaller, all of the available fractional twists all formed Moebius rings, but that the composite numbers did so only for some twists, but not others. Once I knew this for sure, I was fairly confident that I had developed a novel algorithm for identifying primes, but it was much too tedious to do by hand, so I would need a computer program to even think about making it useful. I didn't know whether it was any better than extant algorithms, such as trial division, but I thought it might be made so. There are certain parings that can be done to it - for example, the right half of each graph is redundant, mirroring the left half, so the right side of each graph can be dispensed with. Also, since 1/S and S-1/S are always "Moebius columns", those columns aren't needed. I'm not sure how much more paring can be done, but I hope some more can. Unfortunately, I'm neither a mathematcian nor a programmer, so I haven't really done it justice, and I'm hoping somone on the web will take an interest, and try to develop it further.
"Some say God is living there [in space]. I was looking around very attentively, but I did not see anyone there. I did not detect either angels or gods....I don't believe in God. I believe in man - his strength, his possibilities, his reason."
Gherman Titov, Soviet cosmonaut, in The Seattle Daily Ti