prime factor

[fuzzy wozzy]

612307837 = 16333 x 37489 = 1abc3 x 3def9

                     1  6  3  3  3      1  a  b  c  3
                     3  7  4  8  9      3  d  e  f  9

                     reversed                                               unreversed
----------------------------------------------------          -------------------------------------------------
                   6   1   2   3   0   7   8   3   7                6   1   2   3   0   7   8   3   7
                   3*                                                                                          2   7*
                   3*  1*                                                                                5   1 <-- (9c+3f)
(3a+d) -->   2   5                                                                                  5   3*
                        6   2*                                                                       6   3 <-- (9b+3e+cf) 
(3b+e+ad) -->  5   5                                                                        6   8*
                             7   3*                                                        1   1   1  <-- (9a+3d+fb+ce)
(3c+f+db+ae) -->  6   2                                                         1   1   7*
                             1   1   0*                                                   9   9      <-- (fa+cd+be+18)
(fa+cd+be+18) -->     9   9                                               1   1   0*
                                  1   1   7*                                         6   2        <-- (3c+f+db+ae)
(9a+3d+fb+ce) -->     1   1   1                                          7   3*
                                            6   8*                               5   5             <-- (3b+e+ad)
(9b+3e+cf) -->                     6   3                                6   2*
                                                 5   3*                     2   5   <-- (3a+d)
(9c+3f) -->                                5   1                       3*  1*
                                                      2   7*                3*
                                                

[fuzzy wozzy]

 (ag1 9 3 0 1) -> 9c + 3f + 0 (number with a last digit of 1, such as 51)
(ag2 9 3 0 101 10) -> 9c + 3f + 0 <= 101 (101 is the upper limit; answers are found within a range of 10)

(find (ag1 9 3 0 1) (ag2 9 3 0 101 10)) \\ 101 -> 91 -> 81 -> ... -> 21 -> 11 -> 1

This is a very complicated process unless someone sees a simple way which I don't...
Sometimes correct answers are given right away, sometimes multiple answers come up with no apparent relation.
For the number 51 above, it's easy to see why the 1, but not why the 5, for the answer...

(define ag1
    N1 N2 N3 A -> (ag1-h 0 0 N1 N2 N3 A []))

(define ag1-h
    10 _ _ _ _ _ Ans -> Ans
    C C0 N1 N2 N3 A Ans -> (ag1-h (+ C 1) 0 N1 N2 N3 A Ans) where (= C0 10)
    C C0 N1 N2 N3 A Ans -> (ag1-h C (+ C0 1) N1 N2 N3 A   (cons [C C0] Ans))
  where (= A (ld (+ (* N1 C) (* N2 C0) N3)))
    C C0 N1 N2 N3 A Ans -> (ag1-h C (+ C0 1) N1 N2 N3 A Ans))

(define ag2
    N1 N2 N3 A Z -> (ag2-h 0 0 N1 N2 N3 A Z []))

(define ag2-h
    10 _ _ _ _ _ _ Ans -> Ans
    C C0 N1 N2 N3 A Z Ans -> (ag2-h (+ C 1) 0 N1 N2 N3 A Z Ans) where (= C0 10)
    C C0 N1 N2 N3 A Z Ans -> (ag2-h C (+ C0 1) N1 N2 N3 A Z  (cons [C C0] Ans))
    where (and (<= (+ N3 (* N1 C) (* N2 C0)) A)
                                      (> (+ N3 (* N1 C) (* N2 C0)) (- A Z)))
    C C0 N1 N2 N3 A Z Ans -> (ag2-h C (+ C0 1) N1 N2 N3 A Z Ans))

(define intpart
   N -> (intcount 0 N))

(define intcount
   N X -> N where (< X 1)
   N X -> (intcount (+ N 1) (- X 1)))

(define find
    L L1 -> (find-h L L1 []))

(define find-h
    [] L1 Ans -> Ans
    [X|Y] L1 Ans -> (find-h Y L1 (cons X Ans)) where (element? X L1)
    [X|Y] L1 Ans -> (find-h Y L1 Ans))

(define ld
    N -> (- N (* 10 (intpart (/ N 10)))))

[fuzzy wozzy]

67 x 67 = 4489  

a7 x b7 = 4489?

         4  4  8  9 

                 4  9

             8  4     <-- (ag1 7 7 0 4), try out one of the possible group values

             8  8

         3  6        <-- here the answer is either [6 6] or [4 9] or [9 4], choose which is element of (ag1 7 7 0 4)

         4  4

    

[fuzzy wozzy]

Replacing (cons [C C0] Ans) in (ag1-h) with (cons [(+ (* N1 C) (* N2 C0) N3) C C0] Ans) gives more helpful information,

and partly explains why (9c + 3f) in the unreversed side in the above example comes out to be 51.

Giving (ag1 9 3 0 1) finds [c f] = [3 8], such that (9x3 + 3x8) is a number whose last digit is 1, which is needed to add to 2,

to match up to 3, the second to last number in 612307837. There are 3 group values that come up, 81, 51, and 21,

with each group value having one or more pair of possible answers. So why should 51 be the answer here, rather than 81 or 21?

The reversed side shows that the correct answer for (9c + 3f) is 51, and I think this means that giving the query (ag1 9 3 0 1) when

the 1 must be added to 2, means that the only correct answer out of 81, 51, 21, is 51 in this case, much as the multiplication table

gives an answer...

[fuzzy wozzy]

For r = p x p, r is known, p is unknown, it's easy to find p, even an infinite number, stack permitting,

could this work in general case, and how? 

[Antti Ylikoski]

https://en.wikipedia.org/wiki/Methods_of_computing_square_roots

AJY

[fuzzy wozzy]

Great observation.

Not only is the calculation so easy, it can calculate as many significant digits as desired.

Square root of 2 has been found up to 10 trillion digits, there's a great interest in this somehow.

[fuzzy wozzy]

 

For r = p x q, r is known, p and q are infinite numbers, p = q or not, it might be easy to find them, by thinking simple.

One puzzling thing about square root of 2 being 10 trillion digits is why it took months and years to find them, instead of hours or even days?

It could be that Shen was not used, hmm...

[fuzzy wozzy]

This is not a method to find square roots.

This is a method to find prime factors of infinite numbers. 

[fuzzy wozzy]

Some basic code soon to follow... 

[fuzzy wozzy]

 \* (factor N M L), N = (hd (p)), M = (length (p)) - 1, L = (r), r = p x p.
 
   (factor 7 6 [5 8 3 5 6 0 1 6 8 7 0 3 2 1]) = [7 6 3 9 1 1 1]
   (factor 6 4 [3 8 6 7 4 7 1 7 2 1]) = [6 2 1 8 9]
   (factor 1 7 [2 3 8 6 0 0 5 0 9 9 9 6 6 0 1] = [1 5 4 4 6 6 9 9] *\

(define factor
    F Len L -> (factor-h F Len (drop 4 L)  (hd (drop 3 L)) (hd (drop 3 L))
                    (+ (* 10 (- (num (take 2 L)) (* F F))) (hd (drop 2 L)))
                        [] 0 0 [] [])
   where (or (> (* F F) 10) (> (* F F) (hd L) ))

    F Len L -> (factor-h F Len (drop 3 L) (hd (drop 2 L)) (hd (drop 2 L))
                    (+ (* 10 (- (hd L) (* F F))) (hd (tl L))) [] 0 0 [] []))  

(define factor-h
    F 0 L Lh Lhp U S C P1 P2 Ans -> (append [F] Ans)

    F Len L Lh Lhp U S C P1 P2 Ans -> (factor-h F (- Len 1) (tl L) (hd L) Lh
                                                  (fr 1 F Lh U C Ans) S 1
                                                  (fr 3 F Lh U C Ans) (fr 4 F Lh U C Ans)
                                                  (fr 2 F Lh U C Ans))
                                                          where (= C 0)

    F Len L Lh Lhp U S C P1 P2 Ans -> (factor-h F Len L Lh Lhp P1 S 1 P1 P2 (append (drop -1 Ans) P2))
                                                 where (= error
                                                   (fr1 1 F (hd L) (fr 1 F Lh U C Ans) C
                                                   (append Ans (fr 2 F Lh U C Ans)) ))

   F Len L Lh Lhp U S C P1 P2 Ans -> (factor-h F (+ Len 1) (append [Lh] L)
                                                  Lhp Lhp (hd S)[(hd S)] 1 (hd S)
                                                  [(- (hd (take -2 Ans)) 1)]
                                                  (append (drop -2 Ans)
                                                          [(- (hd (take -2 Ans)) 1)]))
                                                  where (= 10 (hd (reverse Ans)))

    F Len L Lh Lhp U S C P1 P2 Ans -> (factor-h F (- Len 1) (tl L) (hd L) Lh
                                                  (fr 1 F Lh U C Ans)
                                                  (append (tl S) [(fr 3 F Lh U C Ans)]) 1
                                                  (fr 3 F Lh U C Ans) (fr 4 F Lh U C Ans)
                                                  (append Ans (fr 2 F Lh U C Ans)))
                                                                  where (> (length S) 1)
   
    F Len L Lh Lhp U S C P1 P2  Ans -> (factor-h F (- Len 1) (tl L) (hd L) Lh
                                                   (fr 1 F Lh U C Ans) 
                                                   (append S [(fr 3 F Lh U C Ans)]) 1     
                                                   (fr 3 F Lh U C Ans) (fr 4 F Lh U C Ans)
                                                   (append Ans (fr 2 F Lh U C Ans))))

(define fr
   P F Lh U C Ans -> (from1 P (factor-hh0 Lh U C (desc (axg F F 0 U)) Ans)) where (= C 0)
   P F Lh U C Ans -> (from1 P (factor-hh1 Lh U C (desc (axg F F (mid Ans) U)) Ans)))

(define fr1
   P F Lh U C Ans -> (from1 P (factor-hh2 Lh U C (desc (axg F F (mid Ans) U)) Ans)))

(define factor-hh0
   Lh U C [] Ans -> [errorhh0]
   Lh U C [A] Ans -> [(nxt Lh U A) [(from1 2 A)] 10 [10]]

   Lh U C [X|Y] Ans -> [(nxt Lh U X) [(from1 2 X)] (nxt Lh U (hd Y)) [(from1 2 (hd Y))]]
                           where (>= (nxt Lh U X) (mid [(from1 2 X)]))

   Lh U C [X|Y] Ans -> (factor-hh0 Lh U C Y Ans))

(define factor-hh1
   Lh U C [] Ans -> [999]
   Lh U C [A] Ans -> [(nxt Lh U A) [(from1 2 A)] 10 [10]]

   Lh U C [X|Y] Ans -> [(nxt Lh U X) [(from1 2 X)] (nxt Lh U (hd Y)) [(from1 2 (hd Y))]]
                            where (>= (nxt Lh U X) (mid (append Ans [(from1 2 X)])))

   Lh U C [X|Y] Ans -> (factor-hh1 Lh U C Y Ans))

(define factor-hh2
   Lh U C [] Ans -> [error]
   Lh U C [X|Y] Ans -> [ok] where (>= (nxt Lh U X) (mid [(from1 2 X)]))
   Lh U C [X|Y] Ans -> (factor-hh2 Lh U C Y Ans))
             
(define nxt
   Lh U X -> (num [(- U (hd X)) Lh]))

(define mid
    L -> (adds (timesL L (reverse L))))

(define num
    L -> (num-h (reverse L) 1 0))

(define num-h
    [] Unit Ans -> Ans
    [X|Y] Unit Ans -> (num-h Y (* Unit 10) (+ Ans (* X Unit)) ))
  
(define desc
     L -> (desc-h L (length L) []))

(define desc-h
     L 0 Ans -> (reverse (append L Ans))
     [X|Y] Len Ans -> (desc-h Y (- Len 1) (cons X Ans)) where (greater? (hd X) Y)
     [X|Y] Len Ans -> (desc-h (append Y [X]) Len Ans))

(define greater?
     XH [] -> true
     XH [Y1|Y2] -> false where (not (>= XH (hd Y1)))
     XH [Y1|Y2] -> (greater? XH Y2))

(define max
    L Max -> (max-h L Max []))

(define max-h
    [] _ Ans -> Ans
    [X|Y] Max Ans -> (max-h Y Max (cons X Ans))
      where (and (= (from1 2 X) (from1 3 X))
                              (<= (hd X) Max))
 
    [X|Y] Max Ans -> (max-h Y Max Ans))

(define axg
    N1 N2 N3 Max -> (axg-h N1 N2 N3 Max 0 []))

(define axg-h
    _ _ _ _ 10 Ans -> (clean Ans)
    N1 N2 N3 Max C Ans -> (axg-h N1 N2 N3 Max (+ C 1) Ans)
   where (= (aag1 N1 N2 N3 C) [])

    N1 N2 N3 Max C Ans -> (axg-h N1 N2 N3 Max (+ C 1)
    (cons (max (aag1 N1 N2 N3 C) Max) Ans))
    where (not (= [] (max (aag1 N1 N2 N3 C) Max)))

    N1 N2 N3 Max C Ans -> (axg-h N1 N2 N3 Max (+ C 1) Ans))

(define aag1
    N1 N2 N3 A -> (aag1-h 0 0 N1 N2 N3 A []))

(define aag1-h

    10 _ _ _ _ _ Ans -> Ans

    C C0 N1 N2 N3 A Ans -> (aag1-h (+ C 1) 0 N1 N2 N3 A Ans) where (= C0 10)
    C C0 N1 N2 N3 A Ans -> (aag1-h C (+ C0 1) N1 N2 N3 A
                                  (cons [(+ (* N1 C) (* N2 C0) N3) C C0] Ans))
  where (= A (hd (reverse (splita (reverse [(+ (* N1 C) (* N2 C0) N3)])))))
    C C0 N1 N2 N3 A Ans -> (aag1-h C (+ C0 1) N1 N2 N3 A Ans))

(define split
    L -> (append [(quot (hd L) 10)][(rem (hd L) 10)])
  where (and (= (tl L) []) (>= (hd L) 10))
    L -> [(hd L)] where (and (= (tl L) []) (< (hd L) 10))
    L -> (split0 L []))

(define split0
    [] Ans -> (append (split [(hd Ans)]) (tl Ans))
    [X X1|Y] Ans ->(split0 Y
          (append [(+ X1 (quot X 10))]
        [(rem X 10)] Ans)) where (>= X 10)
  
     [X|Y] Ans -> (split0 Y (append [X] Ans)))

(define splita0
    L -> (if (= L (split (reverse L))) L (splita0 (split (reverse L)))))

(define splita
    L -> (splita0 (split L)))

(define rem
    N D -> N where (< N D)
    N D -> (rem (- N D) D))

(define quot
    L N -> (intpart (/ L N)))

(define intcount
   N X -> N where (< X 1)
   N X -> (intcount (+ N 1) (- X 1)))

(define intpart
   N -> (intcount 0 N))

(define take0
   0 M _ -> (reverse M)
   N M [X|Y] -> (take0 (- N 1) (cons X M) Y))

(define take
    N L -> (if (< N 0) (drop (- (length L) (abs N)) L) (take0 N [] L)))

(define drop
      0 L -> L
      N L -> (if (< N 0) (take (- (length L) (abs N)) L) (drop (- N 1) (tl L))))

(define add0
    [] N -> N
   [X|Y] N -> (if (= X null) (add0 Y N) (add0 Y (+ N X))))

(define adds
 L -> [] where (= L []) 
 L -> (add0 L 0))

(define timesL
   _ [] -> []
   _ [err] -> [[null multiply]]
   _ [err1] -> [unequal length]
   L M -> (timesL _ [err1]) where (not (= (length L) (length M)))
   L M -> (if (or (= (hd L) null) (= (hd M) null)) (timesL _ [err]) (reverse (timesL0 L M []))))

(define timesL0
      _ [] A -> A
   [X|Y][P|Q] A -> (timesL0 Y Q (cons (* X P) A)))

(define clean
      [] -> []
   [X|Y] -> (if (or (symbol? X) (number? X)) (append [X] (clean Y)) (append X (clean Y))))

(define cleanall
      L -> (if (= (clean L) L) L (cleanall (clean L))))

(define abs
   N -> (* N -1) where (< N 0)
   N -> N)

(define from1
    1 L -> (hd L)
    N L -> (from1 (- N 1) (tl L)))

(define from
    0 L -> (hd L)
    N L -> (from (- N 1) (tl L)))

[fuzzy wozzy]

Some might call it a paradox that r = p x q might be easier to solve than r = p x p, while others may disagree. 

[fuzzy wozzy]

Trachtenberg method for finding square roots is mathematically concise and precise and

translates nicely into an algorithm, someone said while the method in the book only goes

so far as finding square roots for an 8 digit number, he can go up to 10 digits.

I think Shen can do one up on it and go up to 12 digits with little trouble, and if ever skilled Shenturian

should get to it, the sky's the limit then, probably.

And there is no need to think about how all this time was wasted when one could have simply adopted

Trachtenberg method for an easy and accurate methodology for square roots, because I think all the

knowledge gained thus far could make things that much easier, the sum being greater than its parts, etc...

 

[fuzzy wozzy]

Suppose that it takes x secs to find square roots of r in r = p x p, where (length r) = 5000,

some might say taking x secs for a 5000 digit number is too slow or too fast, but people are

willing to wait years to find Mersenne prime numbers or prime numbers in general and

possibly for prime factors as well.

Which could mean that finding the right answer is more important than the time one must spend on it,

paradoxically enough, by using less of list for Trachtenberg method for square roots, the calculation speed

might be faster by 1000% to 100000% in some cases, I believe...

 

[Antti Ylikoski]

If the calculation is 50% faster, then it will take one half of the time.

What will happen if the calculation is 100'000% faster?

AJY

Finland

--
You received this message because you are subscribed to a topic in the Google Groups "Shen" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/qilang/uRYLu4YlWmM/unsubscribe.
To unsubscribe from this group and all its topics, send an email to qilang+un...@googlegroups.com.
To post to this group, send email to qil...@googlegroups.com.
Visit this group at https://groups.google.com/group/qilang.
For more options, visit https://groups.google.com/d/optout.

[fuzzy wozzy]

100k% sounds like a lot and it probably is...

There was once a competition for Julia set fractals or something like that,

and someone said one Ocaml version was supposedly 170k times faster or something.

If you have a new computer, newer than 20 years old, you could probably go 100k%

faster just by using mostly list anyway, I think.

I think reversing Trachtenberg method for square roots might be interesting as well,

but that might be a harder way... I'm still working on the original way, not quite done, but

who knows...

[fuzzy wozzy]

While the implementation of the original method is about 97% done, what with debugging to be done, etc,

I think I might hold off on it for now and focus on the reverse method for a little bit.

 

The original method is really short, if you look at it, except for the first 3 digits that use imagined number method

or something like that, the rest is very straightforward and clearly outlined, of course one would have to be sure

that one is or has found the right answer for each answer found, and the Trachtenberg method offers several

solutions for checking the accuracy and correctness of the answer, one of which being what the book calls as

remainder and check, basically once the answers are found then the remainders of both the r in r = p x p, and

of the answers would match if the answers are correct.

The reversal method would make it unnecessary to check whether the answers found are correct or not since

there is a certain sense of guarantee attached to the method that if the answer is not correct then it would not

have been found to be an answer to begin with, etc...

The reversal method would also make it unnecessary to have to use the imagined number system for the first three digits

of the r, as is done and required in the original method, in fact the first two digits of r would not even come into consideration

as far as finding the answers go...

And of course the reversal method would be, at a minimum, about a million % faster, I believe, but I might post 97% done

original method implementation, oh and the reversal method would be just as short if not shorter, and maybe others would

utilize it in some way or come up with their own versions which might even go 1 trillion % faster?