Factoring[8 616 460 799] like 100 years ago

09022022, 08:34 PM
Post: #1




Factoring[8 616 460 799] like 100 years ago
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 

09022022, 11:46 PM
Post: #2




RE: Factoring[8 616 460 799] like 100 years ago
Interesting video. Thank you for sharing.
I assume it works similar to: HP 41C: Fermat Factorization (07082014 02:06 PM)Gerald H Wrote: The number 8616460799 is factorized in 695 s.Cf. Jevons' Number 

09032022, 07:35 PM
Post: #3




RE: Factoring[8 616 460 799] like 100 years ago
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. 4147. 

09042022, 06:45 AM
Post: #4




RE: Factoring[8 616 460 799] like 100 years ago
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 

09042022, 05:28 PM
Post: #5




RE: Factoring[8 616 460 799] like 100 years ago
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.artsetmetiers.net Just enter "Carissan" into the search mask. 

09052022, 08:30 AM
Post: #6




RE: Factoring[8 616 460 799] like 100 years ago
Thanks Thomas  great photos! I was aware of the Musée des Arts et Métiers and it's on my mustsee list if I go to Paris, but I wasn't aware of this website. I will have an explore!


09052022, 07:24 PM
(This post was last modified: 09052022 07:34 PM by C.Ret.)
Post: #7




RE: Factoring[8 616 460 799] like 100 years ago
Was für eine beeindruckende rotierende Zahlfaktormaschine!
(09032022 07:35 PM)Thomas Puettmann Wrote: My machine factors Jevons' number in less than 2 min.Humm, nice, much faster than my Ti58C... (09032022 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 Ti58C ! 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? 

09062022, 04:51 PM
Post: #8




RE: Factoring[8 616 460 799] like 100 years ago
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 } 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 FischerTechnik 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". 

09082022, 09:20 AM
(This post was last modified: 09082022 09:23 AM by C.Ret.)
Post: #9




RE: Factoring[8 616 460 799] like 100 years ago
(09062022 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. 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 Ti58c. 

09082022, 04:07 PM
Post: #10




RE: Factoring[8 616 460 799] like 100 years ago
(09082022 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. (09082022 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. (09082022 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. (09082022 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 Ti58c. Thank you very much for your very interesting questions and comments! 

09082022, 05:53 PM
(This post was last modified: 09082022 08:10 PM by Albert Chan.)
Post: #11




RE: Factoring[8 616 460 799] like 100 years ago
(09052022 07:24 PM)C.Ret Wrote: Why this curious series of numbers { 25 36 21 23 22 29 23 31 } n = (x+y) * (xy) 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, powof2, say 32, is good) 

09082022, 06:31 PM
(This post was last modified: 09122022 04:59 PM by Albert Chan.)
Post: #12




RE: Factoring[8 616 460 799] like 100 years ago
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 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, xy ≥ 1 > x ≥ y+1 This leads to slightly faster version. Code: function fermat(n)  assumed odd n 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)*(xy)n)/4 is integer Code: function fermat(n)  assumed odd n 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 

09082022, 07:04 PM
(This post was last modified: 09082022 07:23 PM by Thomas Puettmann.)
Post: #13




RE: Factoring[8 616 460 799] like 100 years ago
(09082022 05:53 PM)Albert Chan Wrote: Prime base has bad screening power. 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 = (291152)(291+152). 

09092022, 06:47 AM
(This post was last modified: 09092022 06:48 AM by EdS2.)
Post: #14




RE: Factoring[8 616 460 799] like 100 years ago
Thanks for the extra explanations! (And the kind words!)


09092022, 09:36 AM
Post: #15




RE: Factoring[8 616 460 799] like 100 years ago
(09052022 07:24 PM)C.Ret Wrote: There are many mysteries that will have to be explained to us. (09042022 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: 

09092022, 09:45 AM
Post: #16




RE: Factoring[8 616 460 799] like 100 years ago
Good thinking! This too, perhaps
https://en.wikipedia.org/wiki/Lehmer_sieve 

09162022, 04:48 PM
(This post was last modified: 09232022 01:41 AM by Albert Chan.)
Post: #17




RE: Factoring[8 616 460 799] like 100 years ago
(09062022 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^2N) ? 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. 

09172022, 08:20 AM
(This post was last modified: 09172022 08:27 AM by Thomas Puettmann.)
Post: #18




RE: Factoring[8 616 460 799] like 100 years ago
(09162022 04:48 PM)Albert Chan Wrote: Why test for isSqr(N+y^2), instead of more efficient isSqr(x^2N) ? 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. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)