# Find the Inverse Neighbor Pairs

### Definition

We say a pair of integers $$\(a,b)\$$, where $$\0 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.

• Nice challenge! Do the neighbor pairs have a practical use somewhere? Commented Feb 3, 2020 at 8:32

# 05AB1E, 1714 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

• Shouldn't the í be R? You want to swap the pair [a,b] to [b,a] before using the reduce-by-subtraction, not a pair like [10,12] to [01,21]. ;) Commented Feb 3, 2020 at 14:17
• Btw, our answers are the same now, so I'll delete it. I tbh hadn't seen your answer when I posted mine, otherwise I would have suggested it as a golf. Commented Feb 3, 2020 at 14:18
• Yeah you're right.. I'll change í to R thanks @Grimmy and @KevinCruijssen Commented Feb 3, 2020 at 14:55
• .Æ defaults to 2 (similar to other list operators: ι, ã, ...), so you can drop the 2 for a 13: TIO Commented Feb 3, 2020 at 15:01
• Interesting, thanks @Grimmy didn't know that will definitely come in handy :) Commented Feb 3, 2020 at 15:14

# 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]
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

• @ShieruAsakoto the OP does have <= !
– RGS
Commented Feb 3, 2020 at 7:44
• @RGS Yes it does, but I have little knowledge in Jelly and I don't know whether there are <= operators in Jelly Commented Feb 3, 2020 at 8:01
• @ShieruAsakoto there aren’t. One option would be to do >¬ (greater than, not), but there may be a golfier option. Commented Feb 3, 2020 at 8:43
• @ShieruAsakoto thanks fixed code Commented Feb 3, 2020 at 8:53

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

# 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


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

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

• You don't need to use the old array syntax and real(j-i,8) is equivalent to dble in Gfortran. 82 Bytes Try it online! Commented Feb 4, 2020 at 9:36
• In fact, you don't need to make it a real at all, you can just make the 2 real with a decimal point. 79 bytes. Try it online! Commented Feb 4, 2020 at 9:58
• @DeathIncarnate Thanks, didn't think of that! Commented Feb 4, 2020 at 21:51

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

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

# 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

• @Jitse why does your //N work? Because //N divides by N and rounds down, isn't that too permissive?
– RGS
Commented Feb 3, 2020 at 8:46
• @Jitse what I mean is that if x = N+1 then x//N<=1 passes the test but x<=N doesn't. Do you get what I am saying?
– RGS
Commented Feb 3, 2020 at 9:07
• @Jitse imagine N = 11, a = 10, b = 6. Then 2^(10-6) // 11 = 16//11 = 1 but it is not true that 2^4 <= 11. Thus the inequality seems too loose.
– RGS
Commented Feb 3, 2020 at 9:37

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

• Hmm... There's got to be some way to use 1 << b-a rather than pow(2, b-a). Commented Feb 3, 2020 at 16:36
• @S.S.Anne That would limit the maximum difference between $a$ and $b$ to $31$, which IMO is not acceptable. Commented Feb 3, 2020 at 16:48

# bc, 14094 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, 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!

# 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)


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

# Perl 6, 55 bytes

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


Try it online!

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

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

# Japt, 18 bytes

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


Try it

# Wolfram Language (Mathematica), 7371 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.