02-13-2020, 08:30 AM
Post: #1
 pinkman Member Posts: 114 Joined: Mar 2018
Hi everyone.
A small challenge discussed with a friend.

Any number created by a tuple of 4 digits on a square shape of 4 consecutive keys on a standard keypad share a common prime factor.

What is this common factor?
The demonstration of quite easy, you can find it once you have the common factor.

I also ask you to create a brut force algorithm, taking any tuple as defined above and finding the common factor.
Brut force might be funny because there are not a lot of combinations and the algorithm, even if brut force, has lots of possibilities of optimization.

02-13-2020, 05:34 PM
Post: #2
 John Keith Senior Member Posts: 486 Joined: Dec 2013
Point of clarification: Do you actually mean tuples or permutations? Tuples allow repetition, for example 7555 or 4444 would be valid tuples.
02-13-2020, 06:00 PM (This post was last modified: 02-13-2020 06:06 PM by John Keith.)
Post: #3
 John Keith Senior Member Posts: 486 Joined: Dec 2013
Assuming here that you meant permutations, it seems that the two groups on the left side of the keypad, { 1 2 4 5 } and { 4 5 7 8 } share the same common factor.

However, the two groups on the right hand side, { 2 3 5 6 } and { 5 6 8 9 } do not share the same common factor nor any others.

Maybe I am missing something?

Another amusing observation: the "almost square" formed by the digits { 0 1 2 } on the lower left (ignoring the decimal point) share the same common factor as the other two groups on the left side.
02-13-2020, 08:15 PM
Post: #4
 Albert Chan Senior Member Posts: 825 Joined: Jul 2018
(02-13-2020 06:00 PM)John Keith Wrote:  However, the two groups on the right hand side, { 2 3 5 6 } and { 5 6 8 9 } do not share the same common factor nor any others.

It may be the puzzle only allow clockwise or counter-clockwise only ?

gcd(2365, 2563) = 11
gcd(5698, 5896) = 22
02-13-2020, 09:07 PM
Post: #5
 pinkman Member Posts: 114 Joined: Mar 2018
(02-13-2020 05:34 PM)John Keith Wrote:  Point of clarification: Do you actually mean tuples or permutations? Tuples allow repetition, for example 7555 or 4444 would be valid tuples.

Sorry I was at work!

1452
4587
9856
3256
...
Clockwise or counterclockwise.
02-13-2020, 09:09 PM
Post: #6
 pinkman Member Posts: 114 Joined: Mar 2018
(02-13-2020 08:15 PM)Albert Chan Wrote:  gcd(2365, 2563) = 11
gcd(5698, 5896) = 22

You’re almost there! We’re looking for a prime common factor.
02-13-2020, 09:11 PM
Post: #7
 pinkman Member Posts: 114 Joined: Mar 2018
(02-13-2020 08:15 PM)Albert Chan Wrote:  It may be the puzzle only allow clockwise or counter-clockwise only ?

Both. It doesn’t matter.
02-13-2020, 10:52 PM (This post was last modified: 02-14-2020 12:09 AM by Albert Chan.)
Post: #8
 Albert Chan Senior Member Posts: 825 Joined: Jul 2018
(02-13-2020 09:09 PM)pinkman Wrote:
(02-13-2020 08:15 PM)Albert Chan Wrote:  gcd(2365, 2563) = 11
gcd(5698, 5896) = 22

You’re almost there! We’re looking for a prime common factor.

From above 1 case, the common prime factor is 11.

To prove, say, "counter-clockwise" number is divisible by 11
Modulo 11, for least significant digits, say x, at the 4 corners:
1. x + (x+1)*10 + (x-2)*100 + (x-3)*1000 ≡ x - (x+1) + (x-2) - (x-3) ≡ 0
2. x + (x-3)*10 + (x-4)*100 + (x-1)*1000 ≡ x - (x-3) + (x-4) - (x-1) ≡ 0
3. x + (x-1)*10 + (x+2)*100 + (x+3)*1000 ≡ x - (x-1) + (x+2) - (x+3) ≡ 0
4. x + (x+3)*10 + (x+4)*100 + (x+1)*1000 ≡ x - (x+3) + (x+4) - (x+1) ≡ 0

For the "clockwise" numbers, just imagine the weight of 1,10,100,1000 are reversed.
Modulo 11, we still get the RHS result, since 100≡1, 1000≡10≡-1
02-14-2020, 12:00 AM
Post: #9
 Albert Chan Senior Member Posts: 825 Joined: Jul 2018
Code:
function gcd(a, b)     if b==0 then return a end     return gcd(b, a%b) end function all_gcds()     t = {{5,4,1,2},{5,2,3,6},{5,6,9,8},{5,8,7,4}}     t_table = {__index = function(F,i) return F[1+(i-1)%4] end}     for i=1,#t do         local a = setmetatable(t[i], t_table)   -- allow wrap around         for j=1,4 do                            -- 4 corners             local d = 1000*a[j] + 10*a[j+2]             local x = d + 100*a[j+1] + a[j+3]             local y = d + 100*a[j+3] + a[j+1]             print(x,y,gcd(x,y))         end     end end

Above is my brute-force Lua code.
Only 16 cases, all of them included the "5", common prime factor = 11

lua> all_gcds()
5412 ﻿ ﻿ ﻿ ﻿ 5214 ﻿ ﻿ ﻿ ﻿ 66
4125 ﻿ ﻿ ﻿ ﻿ 4521 ﻿ ﻿ ﻿ ﻿ 33
1254 ﻿ ﻿ ﻿ ﻿ 1452 ﻿ ﻿ ﻿ ﻿ 66
2541 ﻿ ﻿ ﻿ ﻿ 2145 ﻿ ﻿ ﻿ ﻿ 33
5236 ﻿ ﻿ ﻿ ﻿ 5632 ﻿ ﻿ ﻿ ﻿ 44
2365 ﻿ ﻿ ﻿ ﻿ 2563 ﻿ ﻿ ﻿ ﻿ 11
3652 ﻿ ﻿ ﻿ ﻿ 3256 ﻿ ﻿ ﻿ ﻿ 44
6523 ﻿ ﻿ ﻿ ﻿ 6325 ﻿ ﻿ ﻿ ﻿ 11
5698 ﻿ ﻿ ﻿ ﻿ 5896 ﻿ ﻿ ﻿ ﻿ 22
6985 ﻿ ﻿ ﻿ ﻿ 6589 ﻿ ﻿ ﻿ ﻿ 11
9856 ﻿ ﻿ ﻿ ﻿ 9658 ﻿ ﻿ ﻿ ﻿ 22
8569 ﻿ ﻿ ﻿ ﻿ 8965 ﻿ ﻿ ﻿ ﻿ 11
5874 ﻿ ﻿ ﻿ ﻿ 5478 ﻿ ﻿ ﻿ ﻿ 66
8745 ﻿ ﻿ ﻿ ﻿ 8547 ﻿ ﻿ ﻿ ﻿ 33
7458 ﻿ ﻿ ﻿ ﻿ 7854 ﻿ ﻿ ﻿ ﻿ 66
4587 ﻿ ﻿ ﻿ ﻿ 4785 ﻿ ﻿ ﻿ ﻿ 33
02-14-2020, 06:25 AM
Post: #10
 pinkman Member Posts: 114 Joined: Mar 2018
(02-13-2020 10:52 PM)Albert Chan Wrote:
(02-13-2020 09:09 PM)pinkman Wrote:  You’re almost there! We’re looking for a prime common factor.

From above 1 case, the common prime factor is 11.

To prove, say, "counter-clockwise" number is divisible by 11
Modulo 11, for least significant digits, say x, at the 4 corners:
1. x + (x+1)*10 + (x-2)*100 + (x-3)*1000 ≡ x - (x+1) + (x-2) - (x-3) ≡ 0
2. x + (x-3)*10 + (x-4)*100 + (x-1)*1000 ≡ x - (x-3) + (x-4) - (x-1) ≡ 0
3. x + (x-1)*10 + (x+2)*100 + (x+3)*1000 ≡ x - (x-1) + (x+2) - (x+3) ≡ 0
4. x + (x+3)*10 + (x+4)*100 + (x+1)*1000 ≡ x - (x+3) + (x+4) - (x+1) ≡ 0

For the "clockwise" numbers, just imagine the weight of 1,10,100,1000 are reversed.
Modulo 11, we still get the RHS result, since 100≡1, 1000≡10≡-1

With all my respect!
There is a generic demonstration that factors by 11 , but using congruence is very elegant.
02-14-2020, 06:45 AM (This post was last modified: 02-14-2020 06:47 AM by pinkman.)
Post: #11
 pinkman Member Posts: 114 Joined: Mar 2018
Following Albert’s idea using congruence:

Because:
1000≡-1 (mod 11)
100≡1 (mod 11)
10≡-1 (mod 11)
1≡1 (mod 11)

Then:
A*1000+B*100+C*10+D≡-A+B-C+D (mod 11)
-A+B-C+D=-(A-B+C-D)=0 because the sum of the subtraction of vertices is always 0.
So : A*1000+B*100+C*10+D≡0 (mod 11)

02-14-2020, 11:57 AM (This post was last modified: 02-14-2020 12:00 PM by Albert Chan.)
Post: #12
 Albert Chan Senior Member Posts: 825 Joined: Jul 2018
(02-14-2020 06:45 AM)pinkman Wrote:  A*1000+B*100+C*10+D≡-A+B-C+D (mod 11)

Another perspective, RHS = (B+D) - (A+C), or differences of the diagonals.

For the keypad (or its rotations, or flipped over)

7 8 9
4 5 6
1 2 3

For any 2x2 squares, diagonals sum to the same number, thus (B+D) - (A+C) = 0
02-14-2020, 12:07 PM
Post: #13
 pinkman Member Posts: 114 Joined: Mar 2018
(02-14-2020 11:57 AM)Albert Chan Wrote:
(02-14-2020 06:45 AM)pinkman Wrote:  A*1000+B*100+C*10+D≡-A+B-C+D (mod 11)

Another perspective, RHS = (B+D) - (A+C), or differences of the diagonals.

For the keypad (or its rotations, or flipped over)

7 8 9
4 5 6
1 2 3

For any 2x2 squares, diagonals sum to the same number, thus (B+D) - (A+C) = 0

Yes, good idea to better explain this step of the demonstration.
02-14-2020, 12:17 PM (This post was last modified: 02-14-2020 01:43 PM by pinkman.)
Post: #14
 pinkman Member Posts: 114 Joined: Mar 2018
I still haven't finished a clean implementation in HPPL, but I think I found an elegant solution in python.
Elegant but brut force (find all numbers and divide them by 11) as I requested.

What I call a 'move' is the path followed by your finger on the keypad between 2 keys.
Suppose you start from the '5' key (coordinates 2x2 on the grid) : you have 8 possible moves : 4 (left, right, up, down) x 2 (clockwise and counter-clockwise). Starting from other keys reduces the number of authorized moves, but the principle is the same.
A move from '5' key is -1 ('4' key), +1 ('6' key), -3 ('2' key) or +3 ('8' key).
To find the number formed by the square, you make 3 moves after having used the initial key, which makes 4 digits.
After a horizontal move (+/-1) you have to make a vertical move (+/-3), and then an horizontal move in the opposite direction of the previous horizontal one, then a vertical move in the opposite direction of the previous vertical one.

Mathematically there are two properties to follow a consecutive square on the keypad :
1- If we call m our first move (being -1, +1, -3 or +3), then the third move is -m.
2- If we call m' our second move (being -1, +1, -3, +3), then you'll have ton constraint |m|≠|m'| (in readable language: +/-1 is followed by +/-3, +/-3 is followed by +/-1).

For each key, the moves are m, m', -m.

PHP Code:
result = []movr = [[3], [-3,3], [-3]]      # authorized moves on each row from bottom to top (first to third)movc = [[1], [-1,1], [-1]]      # authorized moves on each column (left to right)a = 0for i in movr:                  # step accross each row...    for j in movc:              # and accross each column        a += 1                  # name (number) of the key        for k in i:             # start moving along the row            for l in j:         # and along the column                result.append(a*1000 + (a + k)*100 + (a + k + l)*10 + (a + k + l - k))        for k in j:             # then start moving along the column            for l in i:         # and along the row                result.append(a*1000 + (a + k)*100 + (a + k + l)*10 + (a + k + l - k))for i in result:    print(i, " modulo (11) -> ", i %11)

And the result :

Code:
 1452  modulo (11) ->  0 1254  modulo (11) ->  0 2541  modulo (11) ->  0 2563  modulo (11) ->  0 2145  modulo (11) ->  0 2365  modulo (11) ->  0 3652  modulo (11) ->  0 3256  modulo (11) ->  0 4125  modulo (11) ->  0 4785  modulo (11) ->  0 4521  modulo (11) ->  0 4587  modulo (11) ->  0 5214  modulo (11) ->  0 5236  modulo (11) ->  0 5874  modulo (11) ->  0 5896  modulo (11) ->  0 5412  modulo (11) ->  0 5478  modulo (11) ->  0 5632  modulo (11) ->  0 5698  modulo (11) ->  0 6325  modulo (11) ->  0 6985  modulo (11) ->  0 6523  modulo (11) ->  0 6589  modulo (11) ->  0 7458  modulo (11) ->  0 7854  modulo (11) ->  0 8547  modulo (11) ->  0 8569  modulo (11) ->  0 8745  modulo (11) ->  0 8965  modulo (11) ->  0 9658  modulo (11) ->  0 9856  modulo (11) ->  0
02-14-2020, 09:12 PM (This post was last modified: 02-14-2020 09:13 PM by John Keith.)
Post: #15
 John Keith Senior Member Posts: 486 Joined: Dec 2013
Ah, now I understand. For completeness, here is my HP50 version. It requires the libraries ListExt, GoferLists, and Ifactor.

Code:
 \<< { { 1 2 5 4 }       { 2 3 6 5 }       { 5 6 9 8 }       { 4 5 8 7 } } \-> s   \<< 1. 4.     FOR j 0. 1.       FOR k s j GET k 2. MOD { REV } IFT 1. 4.         START DUP NL\->I IFACTOR LGRP SWAP LROLL         NEXT DROP       NEXT     NEXT 32. \->LIST     \<< Intersect     \>> STREAM   \>> \>>
02-14-2020, 10:05 PM
Post: #16
 Albert Chan Senior Member Posts: 825 Joined: Jul 2018
(02-14-2020 11:57 AM)Albert Chan Wrote:
(02-14-2020 06:45 AM)pinkman Wrote:  A*1000+B*100+C*10+D≡-A+B-C+D (mod 11)

Another perspective, RHS = (B+D) - (A+C), or differences of the diagonals.

Here is another, with geometry.
sum of diagonals, if divided by 2, is their mid-point, say point M

M = (B+D)/2 = (A+C)/2

RHS = (B+D) - (A+C) = 2M - 2M = 0
02-14-2020, 10:55 PM (This post was last modified: 02-14-2020 10:55 PM by pinkman.)
Post: #17
 pinkman Member Posts: 114 Joined: Mar 2018
(02-14-2020 09:12 PM)John Keith Wrote:  Ah, now I understand. For completeness, here is my HP50 version. It requires the libraries ListExt, GoferLists, and Ifactor.

Code:
 \<< { { 1 2 5 4 }       { 2 3 6 5 }       { 5 6 9 8 }       { 4 5 8 7 } } \-> s   \<< 1. 4.     FOR j 0. 1.       FOR k s j GET k 2. MOD { REV } IFT 1. 4.         START DUP NL\->I IFACTOR LGRP SWAP LROLL         NEXT DROP       NEXT     NEXT 32. \->LIST     \<< Intersect     \>> STREAM   \>> \>>

Nice!
I don’t have a 50g so I could not try this: instead of hard coding ‘32’, could’nt it be counted during the loops?
02-15-2020, 06:38 PM
Post: #18
 John Keith Senior Member Posts: 486 Joined: Dec 2013