14
\$\begingroup\$

Definitions

Quadratic residues

An integer \$r\$ is called a quadratic residue modulo \$n\$ if there exists an integer \$x\$ such that:

$$x^2\equiv r \pmod n$$

The set of quadratic residues modulo \$n\$ can be simply computed by looking at the results of \$x^2 \bmod n\$ for \$0 \le x \le \lfloor n/2\rfloor\$.

The challenge sequence

We define \$a_n\$ as the minimum number of occurrences of the same value \$(r_0-r_1+n) \bmod n\$ for all pairs \$(r_0,r_1)\$ of quadratic residues modulo \$n\$.

The first 30 terms are:

$$1, 2, 1, 1, 1, 2, 2, 1, 1, 2, 3, 1, 3, 4, 1, 1, 4, 2, 5, 1, 2, 6, 6, 1, 2, 6, 2, 2, 7, 2$$

This is A316975 (submitted by myself).

Example: \$n=10\$

The quadratic residues modulo \$10\$ are \$0\$, \$1\$, \$4\$, \$5\$, \$6\$ and \$9\$.

For each pair \$(r_0,r_1)\$ of these quadratic residues, we compute \$(r_0-r_1+10) \bmod 10\$, which leads to the following table (where \$r_0\$ is on the left and \$r_1\$ is on the top):

$$\begin{array}{c|cccccc} & 0 & 1 & 4 & 5 & 6 & 9\\ \hline 0 & 0 & 9 & 6 & 5 & 4 & 1\\ 1 & 1 & 0 & \color{blue}7 & 6 & 5 & \color{green}2\\ 4 & 4 & \color{magenta}3 & 0 & 9 & \color{red}8 & 5\\ 5 & 5 & 4 & 1 & 0 & 9 & 6\\ 6 & 6 & 5 & \color{green}2 & 1 & 0 & \color{blue}7\\ 9 & 9 & \color{red}8 & 5 & 4 & \color{magenta}3 & 0 \end{array}$$

The minimum number of occurrences of the same value in the above table is \$2\$ (for \$\color{green}2\$, \$\color{magenta}3\$, \$\color{blue}7\$ and \$\color{red}8\$). Therefore \$a_{10}=2\$.

Your task

  • You may either:

    • take an integer \$n\$ and print or return \$a_n\$ (either 0-indexed or 1-indexed)
    • take an integer \$n\$ and print or return the \$n\$ first terms of the sequence
    • take no input and print the sequence forever
  • Your code must be able to process any of the 50 first values of the sequence in less than 1 minute.

  • Given enough time and memory, your code must theoretically work for any positive integer supported by your language.

  • This is .

\$\endgroup\$
12
  • 9
    \$\begingroup\$ Grats on getting a sequence published on OEIS! \$\endgroup\$ Sep 21 '18 at 15:43
  • \$\begingroup\$ @AdmBorkBork Thanks. :) (As a matter of fact, I usually avoid posting an OEIS sequence as-is as a challenge, but I guess that's OK for this one.) \$\endgroup\$
    – Arnauld
    Sep 21 '18 at 16:14
  • 6
    \$\begingroup\$ Doesn't the +n inside the (...)mod n have no effect? If so it's very weird that is part of the definition. \$\endgroup\$ Sep 21 '18 at 17:01
  • 3
    \$\begingroup\$ @JonathanAllan Actually, I made a similar remark in the draft version of the sequence and suggested that it was removed. But I didn't find any clear consensus, nor did I get any feedback about that. (And I seem to recall having seen other sequences with (some_potentially_negative_value + n) mod n.) I think it's better to have it in a programming challenge, though, since the sign of the result depends on the language. \$\endgroup\$
    – Arnauld
    Sep 21 '18 at 17:09
  • 1
    \$\begingroup\$ I've tried to find a direct formula without success. The sequence is multiplicative and on primes it equals a_p = round(p/4), which gives us the values for all squarefree numbers. But the situation seems complicated on powers of primes, and the 3 mod 4 and 1 mod 4 cases need to be handled separately. \$\endgroup\$
    – xnor
    Sep 22 '18 at 16:53

10 Answers 10

5
\$\begingroup\$

MATL, 14 bytes

:UG\u&-G\8#uX<

Try it online! Or verify the first 30 values.

Explanation

:      % Implicit input. Range
U      % Square, element-wise
G      % Push input again
\      % Modulo, element-wise
u      % Unique elements
&-     % Table of pair-wise differences
G      % Push input
\      % Modulo, element-wise
8#u    % Number of occurrences of each element
X<     % Minimum. Implicit display
\$\endgroup\$
4
\$\begingroup\$

Japt -g, 22 20 bytes

Spent too long figuring out what the challenge was actually about, ran out of time for further golfing :\

Outputs the nth term in the sequence. Starts struggling when input >900.

õ_²uUÃâ ïÍmuU
£è¥XÃn

Try it or check results for 0-50


Explanation

                  :Implicit input of integer U
õ                 :Range [1,U]
 _                :Map
  ²               :  Square
   uU             :  Modulo U
     Ã            :End map
      â           :Deduplicate
        ï         :Cartesian product of the resulting array with itself
         Í        :Reduce each pair by subtraction
          m       :Map
           uU     :  Absolute value of modulo U
\n                :Reassign to U
£                 :Map each X
 è                :  Count the elements in U that are
  ¥X              :   Equal to X
    Ã             :End map
     n            :Sort
                  :Implicitly output the first element in the array
\$\endgroup\$
4
\$\begingroup\$

Jelly,  13  10 bytes

-1 thanks to Dennis (forcing dyadic interpretation with a leading ð)
-2 more also thanks to Dennis (since the pairs may be de-duplicated we can avoid an R and a 2)

ðp²%QI%ĠẈṂ

A monadic link accepting a positive integer which yields a non-negative integer.

Try it online! Or see the first 50 terms.

How?

ðp²%QI%ĠẈṂ - Link: integer, n                   e.g. 6
ð          - start a new dyadic chain - i.e. f(Left=n, Right=n)
 p         - Cartesian product of (implicit ranges)  [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6]]
  ²        - square (vectorises)                     [[1,1],[1,4],[1,9],[1,16],[1,25],[1,36],[4,1],[4,4],[4,9],[4,16],[4,25],[4,36],[9,1],[9,4],[9,9],[9,16],[9,25],[9,36],[16,1],[16,4],[16,9],[16,16],[16,25],[16,36],[25,1],[25,4],[25,9],[25,16],[25,25],[25,36],[36,1],[36,4],[36,9],[36,16],[36,25],[36,36]]
   %       - modulo (by Right) (vectorises)          [[1,1],[1,4],[1,3],[1,4],[1,1],[1,0],[4,1],[4,4],[4,3],[4,4],[4,1],[4,0],[3,1],[3,4],[3,3],[3,4],[3,1],[3,0],[4,1],[4,4],[4,3],[4,4],[4,1],[4,0],[1,1],[1,4],[1,3],[1,4],[1,1],[1,0],[0,1],[0,4],[0,3],[0,4],[0,1],[0,0]]
    Q      - de-duplicate                            [[1,1],[1,4],[1,3],[1,0],[4,1],[4,4],[4,3],[4,0],[3,1],[3,4],[3,3],[3,0],[0,1],[0,4],[0,3],[0,0]]
     I     - incremental differences (vectorises)    [0,3,2,-1,-3,0,-1,-4,-2,1,0,-3,1,4,3,0]
      %    - modulo (by Right) (vectorises)          [0,3,2,5,3,0,5,2,4,1,0,3,1,4,3,0]
       Ġ   - group indices by value                  [[1,6,11,16],[10,13],[3,8],[2,5,12,15],[9,14],[4,7]]
        Ẉ  - length of each                          [3,2,2,4,2,2]
         Ṃ - minimum                                 2
\$\endgroup\$
0
3
\$\begingroup\$

05AB1E, 22 20 15 13 bytes

LnI%êãÆI%D.m¢

-2 bytes thanks to @Mr. Xcoder.

Try it online or verify the first 99 test cases (in about 3 seconds). (NOTE: The Python legacy version is used on TIO instead of the new Elixir rewrite. It's about 10x faster, but requires a trailing ¬ (head) because .m returns a list instead of a single item, which I've added to the footer.)

Explanation:

L       # Create a list in the range [1, (implicit) input]
 n      # Square each
  I%    # And then modulo each with the input
    ê   # Sort and uniquify the result (faster than just uniquify apparently)
 ã      # Create pairs (cartesian product with itself)
  Æ     # Get the differences between each pair
   I%   # And then modulo each with the input
D.m     # Take the least frequent number (numbers in the legacy version)
   ¢    # Take the count it (or all the numbers in the legacy version, which are all the same)
        # (and output it implicitly)
\$\endgroup\$
2
  • \$\begingroup\$ Ýns%ÙãÆI%D.m¢. (not in legacy, in the new version) \$\endgroup\$
    – Mr. Xcoder
    Sep 21 '18 at 18:01
  • \$\begingroup\$ @Mr.Xcoder Ah, I'm an idiot to use instead of ã.. >.> And didn't knew the .m acted differently in the Elixir rewrite. I originally had the new version, but switched to the legacy after I noticed the ¥ wasn't working (which you've fixed with the Æ). I still use the legacy on TIO though, because it's way faster for this challenge. \$\endgroup\$ Sep 21 '18 at 19:21
3
\$\begingroup\$

C (gcc), 202 200 190 188 187 186 bytes

  • Saved two twelve fourteen fifteen bytes thanks to ceilingcat.
  • Saved a byte.
Q(u,a){int*d,*r,A[u],t,i[a=u],*c=i,k;for(;a--;k||(*c++=a*a%u))for(k=a[A]=0,r=i;r<c;)k+=a*a%u==*r++;for(r=c;i-r--;)for(d=i;d<c;++A[(u+*r-*d++)%u]);for(t=*A;++a<u;t=k&&k<t?k:t)k=A[a];u=t;}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ @ceilingcat Cool; declaring another integer actually allows to save another byte. \$\endgroup\$ Sep 25 '18 at 20:53
  • \$\begingroup\$ @ceilingcat I think those expressions are not equivalent as I need the smallest positive modulo residue. \$\endgroup\$ Dec 19 '18 at 7:39
1
\$\begingroup\$

Python 2, 97 bytes

def f(n):r={i*i%n for i in range(n)};r=[(s-t)%n for s in r for t in r];return min(map(r.count,r))

Try it online!

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

K (ngn/k), 29 bytes

{&/#:'=,/x!r-\:r:?x!i*i:!x}

Try it online!

{ } function with argument x

!x integers from 0 to x-1

i: assign to i

x! mod x

? unique

r: assign to r

-\: subtract from each left

r-\:r matrix of all differences

x! mod x

,/ concatenate the rows of the matrix

= group, returns a dictionary from unique values to lists of occurrence indices

#:' length of each value in the dictionary

&/ minimum

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

Wolfram Language (Mathematica), 64 bytes

Min[Last/@Tally@Mod[Tuples[Union@Mod[Range@#^2,#],2].{1,-1},#]]&

Try it online!

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

Ruby, 88 bytes

->n{(z=(w=(0..n).map{|x|x*x%n}|[]).product(w).map{|a,b|(a-b)%n}).map{|c|z.count(c)}.min}

Try it online!

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

APL (Dyalog Unicode), 28 24 bytes

{⌊/⊢∘≢⌸∊⍵|∘.-⍨∪⍵|×⍨⍳⍵+1}

Try it online!

Prefix direct function. Uses ⎕IO←0.

Thanks to Cows quack for 4 bytes!

How:

{⌊/⊢∘≢⌸∊⍵|∘.-⍨∪⍵|×⍨⍳⍵+1} ⍝ Dfn, argument ⍵

                   ⍳⍵+1 ⍝ Range [0..⍵]
                 ×⍨     ⍝ Squared
               ⍵|       ⍝ Modulo ⍵
              ∪         ⍝ Unique
          ∘.-⍨          ⍝ Pairwise subtraction table
       ∊⍵|              ⍝ Modulo ⍵, flattened
      ⌸                 ⍝ Key; groups indices (in its ⍵) of values (in its ⍺).
   ⊢∘≢                  ⍝ Tally (≢) the indices. This returns the number of occurrences of each element.
 ⌊/                      ⍝ Floor reduction; returns the smallest number.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Couple of small byte-shavings, 2*⍨×⍨, r←¨⊂r∘.-⍨, {≢⍵}⊢∘≢ \$\endgroup\$
    – user41805
    Sep 26 '18 at 7:20

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.