Mixing
Quadratic residues are so much fun!
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
Definitions
Quadratic residues
An integer $r$ is called a quadratic residue modulo $n$ if there exists an integer $x$ such that:
$$x^2equiv 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 < x le lfloor n/2rfloor$.
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):
$$beginarrayc
& 0 & 1 & 4 & 5 & 6 & 9\
hline
0 & 0 & 9 & 6 & 5 & 4 & 1\
1 & 1 & 0 & colorblue7 & 6 & 5 & colorgreen2\
4 & 4 & colormagenta3 & 0 & 9 & colorred8 & 5\
5 & 5 & 4 & 1 & 0 & 9 & 6\
6 & 6 & 5 & colorgreen2 & 1 & 0 & colorblue7\
9 & 9 & colorred8 & 5 & 4 & colormagenta3 & 0
endarray$$
The minimum number of occurrences of the same value in the above table is $2$ (for $colorgreen2$, $colormagenta3$, $colorblue7$ and $colorred8$). 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 code-golf.
code-golf sequence number-theory
asked 1 hour ago
Arnauld
64.6k580273
add a comment |Â
up vote
5
down vote
favorite
Definitions
Quadratic residues
An integer $r$ is called a quadratic residue modulo $n$ if there exists an integer $x$ such that:
$$x^2equiv 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 < x le lfloor n/2rfloor$.
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):
$$beginarrayc
& 0 & 1 & 4 & 5 & 6 & 9\
hline
0 & 0 & 9 & 6 & 5 & 4 & 1\
1 & 1 & 0 & colorblue7 & 6 & 5 & colorgreen2\
4 & 4 & colormagenta3 & 0 & 9 & colorred8 & 5\
5 & 5 & 4 & 1 & 0 & 9 & 6\
6 & 6 & 5 & colorgreen2 & 1 & 0 & colorblue7\
9 & 9 & colorred8 & 5 & 4 & colormagenta3 & 0
endarray$$
The minimum number of occurrences of the same value in the above table is $2$ (for $colorgreen2$, $colormagenta3$, $colorblue7$ and $colorred8$). 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 code-golf.
code-golf sequence number-theory
asked 1 hour ago
Arnauld
64.6k580273
God dammit, I thought number theory would be the last time I saw these shits
– Rushabh Mehta
1 hour ago
4
Grats on getting a sequence published on OEIS!
– AdmBorkBork
57 mins ago
@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.)
– Arnauld
25 mins ago
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
Definitions
Quadratic residues
An integer $r$ is called a quadratic residue modulo $n$ if there exists an integer $x$ such that:
$$x^2equiv 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 < x le lfloor n/2rfloor$.
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):
$$beginarrayc
& 0 & 1 & 4 & 5 & 6 & 9\
hline
0 & 0 & 9 & 6 & 5 & 4 & 1\
1 & 1 & 0 & colorblue7 & 6 & 5 & colorgreen2\
4 & 4 & colormagenta3 & 0 & 9 & colorred8 & 5\
5 & 5 & 4 & 1 & 0 & 9 & 6\
6 & 6 & 5 & colorgreen2 & 1 & 0 & colorblue7\
9 & 9 & colorred8 & 5 & 4 & colormagenta3 & 0
endarray$$
The minimum number of occurrences of the same value in the above table is $2$ (for $colorgreen2$, $colormagenta3$, $colorblue7$ and $colorred8$). 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 code-golf.
code-golf sequence number-theory
asked 1 hour ago
Arnauld
64.6k580273
Definitions
Quadratic residues
An integer $r$ is called a quadratic residue modulo $n$ if there exists an integer $x$ such that:
$$x^2equiv 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 < x le lfloor n/2rfloor$.
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):
$$beginarrayc
& 0 & 1 & 4 & 5 & 6 & 9\
hline
0 & 0 & 9 & 6 & 5 & 4 & 1\
1 & 1 & 0 & colorblue7 & 6 & 5 & colorgreen2\
4 & 4 & colormagenta3 & 0 & 9 & colorred8 & 5\
5 & 5 & 4 & 1 & 0 & 9 & 6\
6 & 6 & 5 & colorgreen2 & 1 & 0 & colorblue7\
9 & 9 & colorred8 & 5 & 4 & colormagenta3 & 0
endarray$$
The minimum number of occurrences of the same value in the above table is $2$ (for $colorgreen2$, $colormagenta3$, $colorblue7$ and $colorred8$). 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 code-golf.
code-golf sequence number-theory
code-golf sequence number-theory
asked 1 hour ago
Arnauld
64.6k580273
asked 1 hour ago
Arnauld
64.6k580273
edited 2 mins ago
asked 1 hour ago
Arnauld
64.6k580273
asked 1 hour ago
Arnauld
64.6k580273
asked 1 hour ago
Arnauld
64.6k580273
64.6k580273
God dammit, I thought number theory would be the last time I saw these shits
– Rushabh Mehta
1 hour ago
4
Grats on getting a sequence published on OEIS!
– AdmBorkBork
57 mins ago
@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.)
– Arnauld
25 mins ago
add a comment |Â
God dammit, I thought number theory would be the last time I saw these shits
– Rushabh Mehta
1 hour ago
4
Grats on getting a sequence published on OEIS!
– AdmBorkBork
57 mins ago
@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.)
– Arnauld
25 mins ago
God dammit, I thought number theory would be the last time I saw these shits
– Rushabh Mehta
1 hour ago
God dammit, I thought number theory would be the last time I saw these shits
– Rushabh Mehta
1 hour ago
4
4
Grats on getting a sequence published on OEIS!
– AdmBorkBork
57 mins ago
Grats on getting a sequence published on OEIS!
– AdmBorkBork
57 mins ago
@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.)
– Arnauld
25 mins ago
@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.)
– Arnauld
25 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
MATL, 14 bytes
:UGu&-G8#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
answered 48 mins ago
Luis Mendo
72.7k885284
add a comment |Â
up vote
2
down vote
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.
õ_²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 element in U that are
Â¥X : Equal to X
à :End map
n :Sort
:Implicitly output the first element in the array
answered 19 mins ago
Shaggy
16.7k21661
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
MATL, 14 bytes
:UGu&-G8#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
answered 48 mins ago
Luis Mendo
72.7k885284
add a comment |Â
up vote
3
down vote
MATL, 14 bytes
:UGu&-G8#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
answered 48 mins ago
Luis Mendo
72.7k885284
add a comment |Â
up vote
3
down vote
up vote
3
down vote
MATL, 14 bytes
:UGu&-G8#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
answered 48 mins ago
Luis Mendo
72.7k885284
MATL, 14 bytes
:UGu&-G8#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
answered 48 mins ago
Luis Mendo
72.7k885284
edited 43 mins ago
answered 48 mins ago
Luis Mendo
72.7k885284
answered 48 mins ago
Luis Mendo
72.7k885284
answered 48 mins ago
Luis Mendo
72.7k885284
72.7k885284
add a comment |Â
add a comment |Â
up vote
2
down vote
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.
õ_²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 element in U that are
Â¥X : Equal to X
à :End map
n :Sort
:Implicitly output the first element in the array
answered 19 mins ago
Shaggy
16.7k21661
add a comment |Â
up vote
2
down vote
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.
õ_²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 element in U that are
Â¥X : Equal to X
à :End map
n :Sort
:Implicitly output the first element in the array
answered 19 mins ago
Shaggy
16.7k21661
add a comment |Â
up vote
2
down vote
up vote
2
down vote
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.
õ_²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 element in U that are
Â¥X : Equal to X
à :End map
n :Sort
:Implicitly output the first element in the array
answered 19 mins ago
Shaggy
16.7k21661
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.
õ_²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 element in U that are
Â¥X : Equal to X
à :End map
n :Sort
:Implicitly output the first element in the array
answered 19 mins ago
Shaggy
16.7k21661
edited 2 mins ago
answered 19 mins ago
Shaggy
16.7k21661
answered 19 mins ago
Shaggy
16.7k21661
answered 19 mins ago
Shaggy
16.7k21661
16.7k21661
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f172613%2fquadratic-residues-are-so-much-fun%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
God dammit, I thought number theory would be the last time I saw these shits
– Rushabh Mehta
1 hour ago
4
Grats on getting a sequence published on OEIS!
– AdmBorkBork
57 mins ago
@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.)
– Arnauld
25 mins ago