Factoring[8 616 460 799] like 100 years ago

[Thomas Puettmann]

I built an electromechanical factoring machine and applied it to the Jevons' number 8 616 460 799. If you are interested, please take a look:

https://youtu.be/-gBhDNJqEE8

[Thomas Klemm]

Interesting video. Thank you for sharing.
I assume it works similar to: HP 41C: Fermat Factorization

(07-08-2014 02:06 PM)Gerald H Wrote:  The number 8616460799 is factorized in 695 s.

Cf. Jevons' Number

[Thomas Puettmann]

Yes, it uses Fermat factorization in various $Z_k$ simultaneously.

The counter counts the number of chain links $n$ that pass the laser beam. A chain with $k$ links is configured in such a way that the laser beam can pass if $8 616 460 699 + n^2$ is a square mod $k$. If the machine stops the human operator must check whether $8 616 460 699 + n^2$ is a square in $Z$.

My machine factors Jevons' number in less than 2 min. But it takes a quarter of an hour to configure the chains...

A very nice paper on a slightly different factoring machine is

J. Shallit, H.C. Williams, F. Morain, Discovery of a Lost Factoring Machine, Mathematical Intelligencer 17 (3), 1995, pp. 41-47.

[EdS2]

Wonderful - thanks for your machine and exposition Thomas, and for the pointer to that paper!

Quote:Soon we were engaged in an active search for its whereabouts in France. We looked for clues at the Conservatoire National des Arts et Métiers (CNAM), the École Normale Superieure, the Institut Henri Poincaré and the Bibliothèque Nationale (BN), without success. We also were unable to contact the company that built the machine, Maison Chateau Frères- they had apparently gone out of business. When a year of intermittent searching failed, we resorted to what seemed at the time a preposterous idea: we would write a letter to each person named Carissan in France and ask for leads. But how to find all the Carissans? Luckily for us, France Telecom provides a computerized database of telephone numbers via the Minitel, a small terminal provided free of charge to Telecom subscribers

I've posted about your video and some related findings over here

[Thomas Puettmann]

Thanks for posting, EdS2! There are stunning pictures of the Carrisan machine (and of much other high tech from the past) in the phototheque of the Musée des Arts et Métiers:

https://phototheque.arts-et-metiers.net

Just enter "Carissan" into the search mask.

[EdS2]

Thanks Thomas - great photos! I was aware of the Musée des Arts et Métiers and it's on my must-see list if I go to Paris, but I wasn't aware of this website. I will have an explore!

[C.Ret]

Was für eine beeindruckende rotierende Zahlfaktormaschine!

(09-03-2022 07:35 PM)Thomas Puettmann Wrote:  My machine factors Jevons' number in less than 2 min.

Humm, nice, much faster than my Ti-58C...

(09-03-2022 07:35 PM)Thomas Puettmann Wrote:  But it takes a quarter of an hour to configure the chains...

Humm, that's much longer than keying the Jevons' number in my Ti-58C !

But, that is the most interesting part which unfortunately is not shown in the video.

Indeed, what is the trick and how the number 8'616'460'799 is encoded in the strings?
Why this curious series of numbers { 25 36 21 23 22 29 23 31 }
Why aren't they all primes?
What is the link with the length of each chain? How are pieces on the chains spaced ?
What is the relationship of these eight chains to the ten digits of Jeson's number?
...

There are many mysteries that will have to be explained to us.

... Unless all this is just a simple publicity campaign for an upcoming book?

[Thomas Puettmann]

Quote:Indeed, what is the trick and how the number 8'616'460'799 is encoded in the strings?

A brief answer to this question is given in my reply to Thomas Klemm's comment. I will try to explain it in more detail:

You can exclude a number from beeing a square by inspecting its last digit. If the last digit is 2, 3, 7, or 8 then the number is not a square.

The factoring machine performs precisely this test. Not in the decimal system but simultaneously in the 25, 36, ..., 31 number systems.

I assume in the following that the machine should factorize the integer 8 616 460 799.

To configure the chain with 36 links for example, you start at 0 in the counter and crank up to 36. At each number \( n \) in this range you put a "track link" onto the top chain link if the last digit of \( 8 616 460 799 + n^2 \) is not that of a square in the 36 number system (i.e. mod 36).

The machine stops if the last digits of \( 8 616 460 799 + n^2 \) is that of a square in all the number systems above. Then the laser beam can pass without obstruction to the photo transistor. You then have to check manually whether \( 8 616 460 799 + n^2 \) actually is a square integer. If it is not, you let the machine continue. If yes, you factor the number as shown in the video.

Quote:Why this curious series of numbers { 25 36 21 23 22 29 23 31 }
Why aren't they all primes?

You can't make the length of a chain shorter than 20 links. So you use 22 instead of 11, for example.

Additionally, you also want to use powers of primes like in 36 = 4 · 9. For example, the last digit of every binary number is that of a square number (0 or 1). On the other hand, numbers that end on 3 in the 4 number system can be excluded from beeing squares.

In addition to the large factoring machine in the video I also built a minimal machine with only two chains (with 28 and 45 links) and much fewer parts. It is ideally suited to learn this kind of factorization. A video with explanations will follow at some point of time on my channel.

Quote:There are many mysteries that will have to be explained to us.

I am glad that the video brought these questions to you. From my perspective, raising questions is more important than providing answers.

Quote:... Unless all this is just a simple publicity campaign for an upcoming book?

The main purpose of the video is the presentation of the machine. The hint to the book is just a side purpose. If I composed this video for "publicity campaigning for an upcoming book", it would be a total failure, since according to the YouTube statistics almost all of the so far 230 viewers already quitted viewing after 1:45 "task completed".

The vast majority of forum members cannot read German and never had any experience with fischertechnik. As EdS2 puts it in his post "... I could have been a fan of Fischer-Technik if I’d had enough of it…" So, it doesn't make much sense to show the video here in order to sell the book.

What I do appreciate is the feedback for the machine and for my somewhat "nerdy" project/mission "learn math with mechanical models" in general. I deeply believe that every child should be given the opportunity to build a mechanical calculator by itself in order to really understand the concept of a "carry".

[C.Ret]

(09-06-2022 04:51 PM)Thomas Puettmann Wrote:  You can exclude a number from beeing a square by inspecting its last digit. If the last digit is 2, 3, 7, or 8 then the number is not a square.
The factoring machine performs precisely this test. Not in the decimal system but simultaneously in the 25, 36, ..., 31 number systems.
I assume in the following that the machine should factorize the integer 8 616 460 799.
To configure the chain with 36 links for example, you start at 0 in the counter and crank up to 36. At each number \( n \) in this range you put a "track link" onto the top chain link if the last digit of \( 8 616 460 799 + n^2 \) is not that of a square in the 36 number system (i.e. mod 36).
The machine stops if the last digits of \( 8 616 460 799 + n^2 \) is that of a square in all the number systems above. Then the laser beam can pass without obstruction to the photo transistor. You then have to check manually whether \( 8 616 460 799 + n^2 \) actually is a square integer. If it is not, you let the machine continue. If yes, you factor the number as shown in the video.
[...]
You can't make the length of a chain shorter than 20 links. So you use 22 instead of 11, for example.

Thank you very much for these very clear and detailed explanations.

I now understand better why these numbers are not simply prime factors; I hadn't thought of any mechanical constraint. Indeed the simplest common and practical sense; the chains must be longer than the wheel that drives them...
...sometimes the simplest and most pragmatic constraints are the hardest details to pin out.

This is also the point of making such a machine yourself. The realization is certainly easier by using construction sets (Fishertechnics, Lego, Meccano, ...) than building everything from scratch and having to manufacture and design every piece by yourself.

Otherwise, I also wanted to congratulate you on the video which is very well made; good video quality (especially the light is excellent - did you use a white glove box?)
As well as the idea of ​​not commenting in one language or another which makes it accessible to everyone. Now knowing the reason for these eight numbers at the bottom of each channel, I understand better why it could not be effectively shown in the video in a reasonably short time.

I also like the added video after the end which explains using a hand's watch why it should read 3199 and not 3208. It is by building such a system that we understand the limits and discovers the imperfections or shortcomings of any technology and mechanics. This is a very good educational idea.

I hope that the number of viewings will considerably increase and especially that your book will sell decently and will awaken many young vocations.

Anyway, this all piqued my curiosity and I now have a few ideas to try to speed up this factorization on my poor, old and slow Ti-58c.

[Thomas Puettmann]

(09-08-2022 09:20 AM)C.Ret Wrote:  Otherwise, I also wanted to congratulate you on the video which is very well made; good video quality (especially the light is excellent - did you use a white glove box?)

All handmade, developed over the years. A part of my shelf is covered with plotter paper. The light is provided by two fixed and one variable LED panels.

(09-08-2022 09:20 AM)C.Ret Wrote:  As well as the idea of ​​not commenting in one language or another which makes it accessible to everyone. Now knowing the reason for these eight numbers at the bottom of each channel, I understand better why it could not be effectively shown in the video in a reasonably short time.

Actually, you just described the emergence of this video. First, I started to talk in English (for the general audience), then in German (for the fischertechnik freaks), but I was not happy (and, more important, my wife was also not happy). Now only the book cover at the end has a definite language, which was somehow the smallest inconsistency I could come up with.

(09-08-2022 09:20 AM)C.Ret Wrote:  I also like the added video after the end which explains using a hand's watch why it should read 3199 and not 3208. It is by building such a system that we understand the limits and discovers the imperfections or shortcomings of any technology and mechanics. This is a very good educational idea.

A good counter that works reliably at high speeds is high tech. The LEGO Lehmer sieve in EdS2's nice post uses an industrial counter for $50 (and, actually, it uses a fischertechnik relay). I didn't want to surrender at that point. Thus, I decided from the beginning to build a counter with a continuous carry mechanism.

I had a very rewarding discussions about the counter in the last days with the authors Jeffrey Shallit and Hugh Williams of the paper I recommended above. They have a document that shows that the French company who built this beautiful Carissan machine were masters in counters and built them for bicycles, automobiles, and turnstiles.

If you look at the Lehmer sieves, you see something similar. They also used technology that just became readily available: bicycle chains and later film tapes.

To me, this is a good explanation why these factoring machines were invented in this period and not, say, 100 years earlier.

(09-08-2022 09:20 AM)C.Ret Wrote:  Anyway, this all piqued my curiosity and I now have a few ideas to try to speed up this factorization on my poor, old and slow Ti-58c.

Thank you very much for your very interesting questions and comments!

[Albert Chan]

(09-05-2022 07:24 PM)C.Ret Wrote:  Why this curious series of numbers { 25 36 21 23 22 29 23 31 }
Why aren't they all primes?

n = (x+y) * (x-y)
x^2 = n + y^2

Modulo b, both x^2 and y^2 has same list of possibilities.
We want base b, such that x^2 % b has very few candidates, for better screening power.

>>> modsqr = lambda b: set(i*i%b for i in range(b))
>>> modsqr(11)
set([0, 1, 3, 4, 5, 9])
>>> modsqr(12)
set([0, 1, 4, 9])

>>> for i in range(20,41): print i, len(modsqr(i))/i
...
20 0.3
21 0.380952380952
22 0.545454545455
23 0.521739130435
24 0.25
25 0.44
26 0.538461538462
27 0.407407407407
28 0.285714285714
29 0.51724137931
30 0.4
31 0.516129032258
32 0.21875
33 0.363636363636
34 0.529411764706
35 0.342857142857
36 0.222222222222
37 0.513513513514
38 0.526315789474
39 0.358974358974
40 0.225

Prime base has bad screening power.
Perhaps we should have pick base with high screening power? (low ratios)
(with this metric, base 22 is bad, pow-of-2, say 32, is good)

[Albert Chan]

Another way, we can avoid mod screening tests and later square confirmation.
see Algorithm FnPS, https://thesai.org/Downloads/Volume11No1...rithms.pdf

Let r = (x^2 - y^2 - n)/2

If r < 0, we update r, with new x = x+1
If r > 0, we update r, with new y = y+1

Δ(x^2)/2 = x+1/2

Code:

function fermat(n)      -- assumed odd n
    local x, y = ceil(sqrt(n)), 0
    local r = (x*x - n)/2
    repeat
        while r<0 do r=r+(x+0.5); x=x+1 end
        while r>0 do r=r-(y+0.5); y=y+1 end
        print(x,y,r)
    until r==0
    return x-y, x+y     -- factors
end

lua> fermat(8616460799)
92825    141      -27.5
92826    454      -319.5
92827    626      -373
92828    760      -407.5
...
92877    3111    -995.5
92878    3141    -1898
92879    3170    -529
92880    3199    0
89681   96079

Update 1:

For positive n, x-y ≥ 1 --> x ≥ y+1
This leads to slightly faster version.

Code:

function fermat(n)      -- assumed odd n
    local x, y = floor(sqrt(n)), 0
    local r = (x*x - n)/2
    while r ~= 0 do     -- invariant r <= 0
        r, x, y = r+(x-y), x+1, y+1
        while r>0 do r=r-(y+0.5); y=y+1 end
        print(x,y,r)
    end
    return x-y, x+y     -- factors
end

Update 2:

mod 4: odd^2 ≡ 1, even^2 ≡ 0

odd x, even y: n = x^2 - y^2 ≡ 1 - 0 ≡ 1 (mod 4)
even x, odd y: n = x^2 - y^2 ≡ 0 - 1 ≡ 3 (mod 4)

With parity of (x,y) maintained, z = ((x+y)*(x-y)-n)/4 is integer

Code:

function fermat(n)      -- assumed odd n
    local x = floor(sqrt(n+1))
    if n%4 == x%2*2+1 then x = x-1 end
    local y = 1 - x%2   -- x +/- y odd
    local z = ((x+y)*(x-y)-n)/4
    while z ~= 0 do     -- invariant z <= 0
        z, y = z+(x-y), y+3
        while z>0 do z=z-y; y=y+2 end
        x, y = x+2, y-1
        print(x,y,z)
    end
    return x-y, x+y     -- factors
end

lua> fermat(8616460799)
92826    455      -387
92828    761      -584
92830    975      -631
92832    1149     -194
...
92874    3021     -1841
92876    3081     -496
92878    3141     -949
92880    3199     0
89681   96079

[Thomas Puettmann]

(09-08-2022 05:53 PM)Albert Chan Wrote:  Prime base has bad screening power.
Perhaps we should have pick base with high screening power? (low ratios)
(with this metric, base 22 is bad, pow-of-2, say 32, is good)

Yes and no.

The chains are not working independently if the numbers of links have common factors. My machine sieves in total modulo lcm(25, 36, 21, 26, 22, 29, 23, 31) = 18 627 909 300. If you substitute the 22 by 32 you sieve in lcm(25, 36, 21, 26, 32, 29, 23, 31) = 13 547 570 400.

In other words, the 32 excludes many times simultaneously to the 36, the 22 doesn't.

Another point is to save configuration time and material. This is why I was very happy with the 21, 22, 23, 25.

By the way, the numbers are not ordered to their size simply because then the bearing of the two counter wheels do not fit one besides the other.

But precisely the ideas you suggested lead me to the "optimal" didactic machine some time ago: Hand cranked with only two chains with 28 and 45 (or 35 and 36) links. When you factor e.g. 61577 with this machine, you have the first coincidence of two trace links at 82. A straightforward check reveals that 61577 + 82^2 = 68301 is not a square number. Thus, you continue cranking. The next coincidence happens at 152. And 61577 + 152^2 = 291^2. Hence, 61577 = (291-152)(291+152).

[EdS2]

Thanks for the extra explanations! (And the kind words!)

[Thomas Klemm]

(09-05-2022 07:24 PM)C.Ret Wrote:  There are many mysteries that will have to be explained to us.

(09-04-2022 06:45 AM)EdS2 Wrote:  I've posted about your video and some related findings over here

It's worth to link that paper here as well:

Quote:Here’s Lehmer’s paper from 1928:
The Mechanical Combination of Linear Forms

[EdS2]

Good thinking! This too, perhaps
https://en.wikipedia.org/wiki/Lehmer_sieve

[Albert Chan]

(09-06-2022 04:51 PM)Thomas Puettmann Wrote:  The machine stops if the last digits of \( 8 616 460 799 + n^2 \) is that of a square in all the number systems above. Then the laser beam can pass without obstruction to the photo transistor. You then have to check manually whether \( 8 616 460 799 + n^2 \) actually is a square integer. If it is not, you let the machine continue. If yes, you factor the number as shown in the video.

N = x^2 - y^2

Why test for isSqr(N+y^2), instead of more efficient isSqr(x^2-N) ?

N = 8616460799 = 92880^2 - 3199^2

min(y) = 0
y to be tested = 0 to 3199, or 3200 cases

min(x) = ceil(sqrt(N)) = 92825
x to be tested = 92825 to 92880, or 56 cases

We could limit tested x further ...

mod3: N ≡ -1 = 0 - 1 --> x ≡ 0 (mod 3)
mod8: N ≡ -1 = 0 - 1 --> x ≡ 0 (mod 4)      // odd^2 = (4k±1)^2 ≡ 1 (mod 8)

--> x = 92832 to 92880 step 12, or 5 cases.

[Thomas Puettmann]

(09-16-2022 04:48 PM)Albert Chan Wrote:  Why test for isSqr(N+y^2), instead of more efficient isSqr(x^2-N) ?

The reason is to go to automatization as straight as possible.

U. Meyer, who built the LEGO machine, did the same, and I guess for the same reason.

The machine requires a lot of explanation and configuration already. I wanted to avoid any further difficulties.

In order to follow the Fermat method literally, you need to compute
s = ceil(sqrt(N)) = min x (by hand, if you want to be authentic). The number x starting from s does not fit into the counter. The counter hence wouldn't display x nor y but the number of the current step in the Fermat method. The configuration table for a chain with k links would be indexed by (s+n)^2 - N mod k instead of N + n^2 mod k. The "-" looks innocent but from my experience, in practice, it is not.

From what I remember the Lehmers and Carissans never used the Fermat method literally but developed an individual sieving strategy for every single integer they were interested in. This way they could factorize integers of a different magnitude. But, in my opinion, it wouldn't make sense to explain this to a general audience.

Actually, I guess the Lehmers would not even have thought to factorize the Jevons' number on a machine, since they could do it in say 20 min by hand (see the paper of Solomon Golomb in Thomas Klemm's link above).

So, yes, you are absoultely right: I could shorten the runtime significantly, but at the cost of a slightly more difficult configuration and of a less straightforward explanation.