Find the Inverse Neighbor Pairs

Question

Definition

We say a pair of integers \$(a,b)\$, where \$0<a<b<N\$ and \$N\$ is an integer larger than 4, is an inverse neighbor pair respect to \$N\$ if \$ab\equiv1\text{ }(\text{mod }N)\$ and \$1\le b-a\le\log_2{N}\$. There may be no such pairs respect to some integers \$N\$.

To illustrate the definition, consider \$N=14\$. \$(3,5)\$ is an inverse neighbor pair respect to \$N\$ because \$3\times 5=15\equiv1\text{ }(\text{mod }14)\$ and \$1\le 5-3=2\le\log_2{14}\approx 3.807\$. Another pair is \$(9,11)\$.

On the other hand, consider \$N=50\$. \$(13,27)\$ is not an inverse neighbor pair because although \$13\times 27=351\equiv1\text{ }(\text{mod }50)\$, their distance \$27-13=14\$ is too large to be "neighbors". In fact, there are no inverse neighbor pairs respect to this \$N\$, since there are no such pairs that both \$ab\equiv1\text{ }(\text{mod }50)\$ and \$1\le b-a\le\log_2{50}\approx 5.643\$ can be fulfilled.

Challenge

Write a program or function, that given an integer input \$N>4\$, outputs or returns all inverse neighbor pairs respect to \$N\$ without duplicate. You may output them in any reasonable format that can be clearly interpreted as distinct pairs by a human, e.g. two numbers per line, or a list of lists, etc.

The algorithm you use must in theory vaild for all integers \$N>4\$, although practically your program/function may fail or timeout for too large values.

Sample I/O

For inputs without any inverse neighbor pairs, the word empty in the output column means empty output, not the word "empty" literally.

Input  -> Output
5      -> (2,3)
14     -> (3,5), (9,11)
50     -> empty
341    -> (18,19), (35,39), (80,81), (159,163), (178,182), (260,261), (302,306), (322,323)
999    -> (97,103), (118,127), (280,289), (356,362), (637,643), (710,719), (872,881), (896,902)
1729   -> empty
65536  -> (9957,9965), (15897,15913), (16855,16871), (22803,22811), (42725,42733), (48665,48681), (49623,49639), (55571,55579)
65537  -> (2880,2890), (4079,4081), (10398,10406), (11541,11556), (11974,11981), (13237,13249), (20393,20407), (26302,26305), (39232,39235), (45130,45144), (52288,52300), (53556,53563), (53981,53996), (55131,55139), (61456,61458), (62647,62657)
524287 -> (1023,1025), (5113,5127), (59702,59707), (82895,82898), (96951,96961), (105451,105458), (150800,150809), (187411,187423), (192609,192627), (331660,331678), (336864,336876), (373478,373487), (418829,418836), (427326,427336), (441389,441392), (464580,464585), (519160,519174), (523262,523264)

Winning Condition

This is a code-golf challenge, so shortest valid submission of each language wins. Standard loopholes are forbidden by default.

Answer 1

05AB1E, 17 14 13 bytes

Thanks to @KevinCruijssen and @Grimmy for the fix and inspiration from Kevin's now deleted answer

-1 byte further thanks to @Grimmy

L.ÆʒRÆo@}ʒPI%

Try it online!

---

Explanation

L.Æ                    - Combinations of [1..N] with 2 elements
    ʒ     }            - Filter this when ...
     RÆo               - 2^(The difference of each pair) is... 
        @              - <= the input
           ʒPI%        - Then filter this list further where the product modulo input is 1

Answer 2

Jelly, 17 bytes

ŒcðIḢ2*>¬ȧ⁸P%⁼1ðƇ

A monadic Link accepting an integer which yields a list of pairs.

Try it online!

How?

not updated for less-than-or-equal...

ŒcðIḢ2*<ȧ⁸P%⁼1ðƇ - Link: integer, n
Œc               - unordered pairs (of implicit range [1..n])
               Ƈ - filter keep those for which:
  ð           ð  - ...this dyadic chain, f(pair,n), is non-zero:
   I             -   deltas       [a,b] -> [b-a]
    Ḣ            -   head                   b-a
     2*          -   2 raised to         2^(b-a)
       <         -   is less than (n)    2^(b-a)<n  == b-a<log(n,2)
         ⁸       -   chain's left argument, the pair
        ȧ        -   logical AND           [a,b]    or  0
          P      -   product                a×b         0
           %     -   modulo (n)            (a×b)%n      0
            ⁼1   -   equals one?           (a×b)%n==1   0

Answer 3

JavaScript (V8),  61 59  57 bytes

n=>{for(a=b=n;a=a||--b;)--a*b%n-1|2**(b-a)>n||print(a,b)}

Try it online!

The way the for loop is written, we have \$b=N\$ during the first \$N\$ iterations and we have \$a=0\$ before \$b\$ is decremented. But in both cases, it implies \$ab\equiv 0\pmod N\$, so the corresponding pairs are rejected anyway.

Answer 4

MATL, 20 bytes

:2XN!tpG\1=yd|WG>>Z)

The output is a 2-row matrix where each column is a pair.

Try it online!

How it works

Consider input 5 as an example.

:     % Implicit input: N. Range [1 2 ... N]
      % STACK: [1 2 ... N]
2XN   % Combinations of 2 elements, as rows in a 2-column matrix
      % STACK: [1 2;
                1 3;
                ···;
                4 5]
!     % Transpose. Each combination is now a column in a 2-row matrix
      % STACK: [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
tp    % Duplicate. Product of each column
      % STACK: [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
               [2  3  4  5  6  8 10 12 15 20]
G\    % Modulo N
      % STACK: [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
               [2 3 4 0 1 3 0 2 0 0]
1=    % Equal to 1?
      % STACK: [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
               [0 0 0 0 1 0 0 0 0 0]
y     % Push another copy of the 2-row matrix
      % STACK: [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
               [0 0 0 0 1 0 0 0 0 0]
               [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
d|    % Absolute difference between the two rows
      % STACK: [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
               [0 0 0 0 1 0 0 0 0 0]
               [1 2 3 4 1 2 3 1 2 1]
W     % 2 raised to that
      % STACK: [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
               [0 0 0 0 1 0 0 0 0 0]
               [2  4  8 16  2  4  8  2  4  2]
G>    % Greater than N? (**)
      % STACK: [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
               [0 0 0 0 1 0 0 0 0 0]
               [0 0 1 1 0 0 1 0 0 0]
>     % Greater than. This gives true for entries that are true in (*)
      % and false in (**)
      % STACK: [1 1 1 1 2 2 2 3 3 4;
                2 3 4 5 3 4 5 4 5 5]
               [0 0 0 0 1 0 0 0 0 0]
Z)    % Use as a logical index into the columns of the 2-row matrix
      % STACK: [2;
                3]
      % Implicit display

Answer 5

JavaScript (V8), 56 bytes

x=>{for(y=x;i=--y;)for(z=x;z>>=1;)y*++i%x-1||print(y,i)}

Try it online!

This \$O(n\log{n})\$ algorithm works practically up to \$N\approx2^{26.5}\approx9.49\times10^7\$.

This was 67 bytes and was originally for my test case verifications only, and then I saw Arnauld's 57 bytes. Inspired by his solution, I checked whether I can golf the loops while keeping \$O(n\log{n})\$ complexity, and here it is.

Answer 6

Fortran (GFortran), 86 79 bytes

read*,n
print*,((pack([i,j],mod(i*j,n)==1.and.2.**(j-i)<=n),j=i+1,n),i=1,n)
end

-7 bytes thanks to @DeathIncarnate

Yes, I still write Fortran in 2020. Here I'm reading an implicit integer n and looping over i and j (a and b would be implicitly reals). An array (i, j) is masked using the intrinsic pack().

Try it online!

Answer 7

Ruby, 64 bytes

->n{(r=*1...n).product(r).select{|a,b|b>a&&a*b%n==1&&n>=1<<b-a}}

Try it online!

Answer 8

Charcoal, 27 bytes

ＮθＦθＦιＦ‹›Ｘ²⁻ικθ⁼¹﹪×ικθＩ⟦⟦κι

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input N.

ＦθＦι

Loop 0 <= a < b < N. (a=0 can never be a solution, so it doesn't hurt to include it.)

Ｆ‹›Ｘ²⁻ικθ⁼¹﹪×ικθ

Check whether 2**(b-a)<=N and a*b%N==1.

Ｉ⟦⟦κι

If so then output a and b, on separate lines, with each pair double-spaced.

Answer 9

Python 3, 76 71 bytes

lambda N:[(a,b)for a in range(N)for b in range(a)if(1<<a-b)-N<a*b%N==1]

Thanks, Jitse, for saving me 5 bytes after some discussion.

You can try it online, where I'm not running the larger test cases because it times out

Answer 10

C (gcc) -lm, 76 bytes

A port of my JS answer.

a,b;f(n){for(a=b=n;a=a?a:--b;)--a*b%n-1|pow(2,b-a)>n||printf("%d,%d ",a,b);}

Try it online!

Answer 11

bc, 140 94 90 bytes

define f(n){for(a=2;a<n;a=a+1){for(d=1;2^d<=n;d++){if(a*(a+d)%n==1){print" ",a,",",a+d}}}}

Try it online!

Function f() takes the number as input, writes its output to stdout, and returns 0, which should be ignored. The test wrapeper in the TIO needs a special marker for end-of-file, as it otherwise keeps trying to read

Having looked at another answer, I saw I could do \$2^{d}\le{n}\$ instead of \$d\le\log_2{n}\$ -46, including the +2 for -l.

I was amazed to find it turned into a one-liner.

I then realized I had two unneeded pairs of parentheses. -4.

I have also realized that I allow b>n, but it apparently doesn't hit in the test cases.

Edit: it turns out with \$0<a<N<b\$, there can't be a hit unless \${{b-a}\over2}\ge\sqrt{N-1}\$ Combining with the neighbor requirement of \$b-a\le\log_2{N}\$ we get \$2\sqrt{N-1} \le \log_2{N} \$ This only happens at \$N=1\$, so I'm safe.

ungolfed:

define f(n) {
    for (a=2; a<n; a=a+1) {
        for (d=1; 2^d<=n; d++) {
            if (a*(a+d)%n==1) {
                print " ", a, ",", a+d
            }
        }
    }
}

originally: bc -l, 138 + 2 = 140 bytes

define f(n){
scale=9
m=l(n)/l(2)
scale=0
for(a=2;a<n;a=a+1){c=a+m
if(c>=n)c=n
for(b=a+1;b<c;b=b+1){if(((a*b)%n)==1){print " ",a,",",b
}}}}

Try it online!

Answer 12

Burlesque, 46 bytes

riJs1ro2CBf{Jp^.-ab2j**g1.<jpdg1.%1==&&}:U_:so

Try it online!

ri     # Read as int
Js1    # Store a copy
ro     # Range [1,N]
2CB    # Combinations of length 2
f{     # Filter for
 J     # Duplicate
 p^.-  # i-j
 ab    # |i-j|
 2j**  # 2^|i-j|
 g1.<  # < N
 jpd   # i*j
 g1.%  # (i*j)%N
 1==   # Equal to 1
 &&    # Bitwise and
}
:U_    # Filter out i=j
:so    # Filter for sorted (removing duplicates)

Answer 13

Haskell, 57 bytes

A port of my Python answer

f n=[(a,b)|a<-[0..n],b<-[0..a-1],2^(a-b)<=n,1==mod(a*b)n]

You can try it online

Answer 14

Perl 6, 55 bytes

{grep {[*](@^a)%$_==1&&$_>=2**[R-](@a)>=2},(^$_ X ^$_)}

Try it online!

Answer 15

R, 77 64 bytes

function(N)which((o=outer(x<-1:N,x,'-'))>0&2^o<=N&x%o%x%%N==1,T)

Try it online!

Returns a matrix with columns b,a of all inverse neighbor pairs. Since it creates several NxN matrices, this will run out of memory in a hurry.

Answer 16

Husk, 24 bytes

fȯ≤¹`^2F-fȯ=1%¹F*fF>´×,ḣ

Try it online! Nothing too complicated, just the three filters applied to the list of ordered pairs.

Answer 17

Japt, 18 bytes

õ à2 fÈrͧU«1nX×uU

Try it

Answer 18

Wolfram Language (Mathematica), 73 71 69 bytes

n_:>Select[Range@n~Subsets~2,Mod[1##&@@#,n]==1&&2^#[[2]]<=2^#[[1]]n&]

Try it online!

Defined as a delayed rule that can be applied to any integer.