Os resíduos quadráticos são muito divertidos!

13

Definições

Resíduos quadráticos

Um número inteiro é chamado de módulo quadrático de resíduos se existir um número inteiro x tal que:rnx

x2r(modn)

O conjunto de resíduos quadráticos módulo n pode ser simplesmente calculado observando os resultados de x2modn para 0xn/2 .

A sequência do desafio

Definimos an como o número mínimo de ocorrências do mesmo valor (r0r1+n)modn para todos os pares (r0,r1) dos resíduos quadráticos módulo n .

Os primeiros 30 termos são:

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

Este é o A316975 (enviado por mim).

Exemplo: n=10

Os resíduos quadráticos do módulo 10 são 0 , 1 , 4 , 5 , 6 e 9 .

Para cada par (r0,r1) desses resíduos quadráticos, calculamos (r0r1+10)mod10 , o que leva à tabela a seguir (onde r0 está à esquerda e r1 está no topo):

014569009654111076524430985554109666521079985430

O número mínimo de ocorrências do mesmo valor na tabela acima é (para , , e ). Portanto .22378a10=2

Sua tarefa

  • Você pode:

    • pegue um número inteiro e imprima ou retorne (indexado 0 ou indexado 1)nan
    • pegue um número inteiro e imprima ou retorne os primeiros termos da sequênciann
    • não aceite nenhuma entrada e imprima a sequência para sempre
  • Seu código deve ser capaz de processar qualquer um dos 50 primeiros valores da sequência em menos de 1 minuto.
  • Com tempo e memória suficientes, seu código deve funcionar teoricamente para qualquer número inteiro positivo suportado pelo seu idioma.
  • Isso é .
Arnauld
fonte
9
Grats em obter uma sequência publicada no OEIS!
AdmBorkBork
@AdmBorkBork Thanks. :) (Por uma questão de fato, eu normalmente evite postar uma seqüência OEIS como-é como um desafio, mas eu acho que é OK para um presente.)
Arnauld
6
O +ninterior (...)mod nnão tem efeito? Nesse caso, é muito estranho que faça parte da definição.
Jonathan Allan
3
@ JonathanAllan Na verdade, fiz uma observação semelhante na versão preliminar da sequência e sugeri que ela fosse removida. Mas não encontrei nenhum consenso claro, nem recebi feedback sobre isso. (E eu me lembro de ter visto outras seqüências com (some_potentially_negative_value + n) mod n.) Mas acho que é melhor tê-lo em um desafio de programação, já que o sinal do resultado depende da linguagem .
Arnauld 21/09
1
Eu tentei encontrar uma fórmula direta sem sucesso. A sequência é multiplicativa e, nos primos, é igual a_p = round(p/4), o que nos fornece os valores para todos os números sem quadratura. Mas a situação parece complicada com os poderes dos números primos, e os casos de 3 mod 4 e 1 mod 4 precisam ser tratados separadamente.
Xnor

Respostas:

5

MATL , 14 bytes

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

Experimente online! Ou verifique os 30 primeiros valores .

Explicação

:      % 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
Luis Mendo
fonte
4

Japonês -g , 22 20 bytes

Passamos muito tempo a descobrir qual era realmente o desafio e o tempo acabou para continuar a jogar golfe: \

Gera o nth th termo na sequência. Começa a lutar quando a entrada >900.

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

Experimente ou verifique os resultados de 0 a 50


Explicação

                  :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
Shaggy
fonte
4

Geléia ,  13  10 bytes

-1 graças a Dennis (forçando a interpretação diádica com uma liderança ð)
-2 mais também graças a Dennis (como os pares podem ser duplicados, podemos evitar a Re a 2)

ðp²%QI%ĠẈṂ

Um link monádico que aceita um número inteiro positivo que produz um número inteiro não negativo.

Experimente online! Ou veja os 50 primeiros termos .

Quão?

ð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
Jonathan Allan
fonte
3

05AB1E , 22 20 15 13 bytes

LnI%êãÆI%D.m¢

-2 bytes graças a @Mr. Xcoder .

Experimente online ou verifique os primeiros 99 casos de teste (em cerca de 3 segundos) . (OBSERVAÇÃO: A versão herdada do Python é usada no TIO em vez da nova reescrita do Elixir. É cerca de 10x mais rápida, mas requer um trailing ¬(head) porque .mretorna uma lista em vez de um único item, que eu adicionei ao rodapé.)

Explicação:

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)
Kevin Cruijssen
fonte
Ýns%ÙãÆI%D.m¢. (não está no legado, na nova versão)
Mr. Xcoder 21/09
@ Mr.Xcoder Ah, eu sou um idiota de usar em vez de ã..>.> E não sabia o que .magia de maneira diferente na reescrita do Elixir. Originalmente, eu tinha a nova versão, mas mudei para o legado depois que notei que ¥não estava funcionando (que você corrigiu com o Æ). Eu ainda uso o legado no TIO, porque é muito mais rápido para esse desafio.
Kevin Cruijssen 21/09
3

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

  • Economizou dois doze quatorze e quinze bytes graças ao tetocat .
  • Guardou um 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;}

Experimente online!

Jonathan Frech
fonte
@ceilingcat Cool; declarar outro número inteiro permite salvar outro byte.
Jonathan Frech 25/09
@ceilingcat Acho que essas expressões não são equivalentes, pois preciso do menor resíduo de módulo positivo.
Jonathan Frech
1

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

Experimente online!

Chas Brown
fonte
1

K (ngn / k) , 29 bytes

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

Experimente online!

{ } função com argumento x

!xnúmeros inteiros de 0ax-1

i: atribuir a i

x! mod x

? único

r: atribuir a r

-\: subtrair de cada esquerda

r-\:r matriz de todas as diferenças

x! mod x

,/ concatenar as linhas da matriz

= grupo, retorna um dicionário de valores exclusivos para listas de índices de ocorrência

#:' comprimento de cada valor no dicionário

&/ mínimo

ngn
fonte
1

APL (Dyalog Unicode) , 28 24 bytes

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

Experimente online!

Prefixo da função direta. Usos ⎕IO←0.

Graças ao vacas charlatão por 4 bytes!

Quão:

{⌊/⊢∘≢⌸∊⍵|∘.-⍨∪⍵|×⍨⍳⍵+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.
J. Sallé
fonte
1
Par de aparas de byte pequenos, 2*⍨×⍨, r←¨⊂r∘.-⍨, {≢⍵}⊢∘≢
user41805 26/09/18