Challenge - Keypad puzzle

[pinkman]

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.

   

[John Keith]

Point of clarification: Do you actually mean tuples or permutations? Tuples allow repetition, for example 7555 or 4444 would be valid tuples.

[John Keith]

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.

[Albert Chan]

(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

[pinkman]

(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!

Just follow a square, like:
1452
4587
9856
3256
...
Clockwise or counterclockwise.

[pinkman]

(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.

[pinkman]

(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.

[Albert Chan]

(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

[Albert Chan]

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

[pinkman]

(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.

[pinkman]

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)

Original idea and demonstration: https://twitter.com/fermatslibrary/statu...55681?s=21

[Albert Chan]

(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

[pinkman]

(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.

[pinkman]

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.

A few preliminary comments about the methods:
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 = 0
for 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

[John Keith]

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
  \>>
\>>

[Albert Chan]

(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

[pinkman]

(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?

[John Keith]

(02-14-2020 10:55 PM)pinkman Wrote:  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?

32 is the total number of time the loops are executed. Counting them would waste precious machine cycles on an old, slow machine.

Mostly it's just a quick-and-dirty program, unworthy of much optimization IMHO.