14
\$\begingroup\$

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.

\$\endgroup\$
1
  • 5
    \$\begingroup\$ Nice challenge! Do the neighbor pairs have a practical use somewhere? \$\endgroup\$
    – Jitse
    Feb 3 '20 at 8:32

18 Answers 18

5
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ 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]. ;) \$\endgroup\$ Feb 3 '20 at 14:17
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 3 '20 at 14:18
  • 1
    \$\begingroup\$ Yeah you're right.. I'll change í to R thanks @Grimmy and @KevinCruijssen \$\endgroup\$ Feb 3 '20 at 14:55
  • \$\begingroup\$ defaults to 2 (similar to other list operators: ι, ã, ...), so you can drop the 2 for a 13: TIO \$\endgroup\$
    – Grimmy
    Feb 3 '20 at 15:01
  • \$\begingroup\$ Interesting, thanks @Grimmy didn't know that will definitely come in handy :) \$\endgroup\$ Feb 3 '20 at 15:14
3
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ @ShieruAsakoto the OP does have <= ! \$\endgroup\$
    – RGS
    Feb 3 '20 at 7:44
  • \$\begingroup\$ @RGS Yes it does, but I have little knowledge in Jelly and I don't know whether there are <= operators in Jelly \$\endgroup\$ Feb 3 '20 at 8:01
  • 1
    \$\begingroup\$ @ShieruAsakoto there aren’t. One option would be to do (greater than, not), but there may be a golfier option. \$\endgroup\$ Feb 3 '20 at 8:43
  • \$\begingroup\$ @ShieruAsakoto thanks fixed code \$\endgroup\$ Feb 3 '20 at 8:53
2
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ 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! \$\endgroup\$ Feb 4 '20 at 9:36
  • \$\begingroup\$ 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! \$\endgroup\$ Feb 4 '20 at 9:58
  • \$\begingroup\$ @DeathIncarnate Thanks, didn't think of that! \$\endgroup\$
    – Roninkoi
    Feb 4 '20 at 21:51
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 27 bytes

NθFθFιF‹›X²⁻ικθ⁼¹﹪×ικθI⟦⟦κι

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

Nθ

Input N.

FθFι

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

F‹›X²⁻ικθ⁼¹﹪×ικθ

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

I⟦⟦κι

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ @Jitse why does your //N work? Because //N divides by N and rounds down, isn't that too permissive? \$\endgroup\$
    – RGS
    Feb 3 '20 at 8:46
  • \$\begingroup\$ @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? \$\endgroup\$
    – RGS
    Feb 3 '20 at 9:07
  • \$\begingroup\$ @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. \$\endgroup\$
    – RGS
    Feb 3 '20 at 9:37
1
\$\begingroup\$

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!

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

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!

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

Perl 6, 55 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Japt, 18 bytes

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

Try it

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.