Não, eu não quero dizer ϕ = 1.618...
e π = 3.14159...
. Quero dizer as funções .
- φ (x) é o número de números inteiros menores ou iguais aos
x
que são relativamente primos parax
. - π (x) é o número de primos menor ou igual a
x
. - Digamos que "not pi" seja então π̅ (x) e defina-o como o número de compósitos menor ou igual a
x
.
Tarefa
Dado um número inteiro estritamente positivo x
, calcule φ (π̅ (x)) . A pontuação está em bytes.
Exemplos
Cada linha consiste na entrada (de 1 a 100, inclusive) e na saída correspondente separada por um espaço.
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 2
9 2
10 4
11 4
12 2
13 2
14 6
15 4
16 6
17 6
18 4
19 4
20 10
21 4
22 12
23 12
24 6
25 8
26 8
27 16
28 6
29 6
30 18
31 18
32 8
33 12
34 10
35 22
36 8
37 8
38 20
39 12
40 18
41 18
42 12
43 12
44 28
45 8
46 30
47 30
48 16
49 20
50 16
51 24
52 12
53 12
54 36
55 18
56 24
57 16
58 40
59 40
60 12
61 12
62 42
63 20
64 24
65 22
66 46
67 46
68 16
69 42
70 20
71 20
72 32
73 32
74 24
75 52
76 18
77 40
78 24
79 24
80 36
81 28
82 58
83 58
84 16
85 60
86 30
87 36
88 32
89 32
90 48
91 20
92 66
93 32
94 44
95 24
96 70
97 70
98 24
99 72
100 36
Use este link para calcular a saída esperada para qualquer entrada. Além disso, uma lista de entradas e saídas x <= 1000
é fornecida aqui em pastebin . (Gerado com este programa Minkolang .)
Classificação
Aqui está um snippet de pilha para gerar uma classificação regular e uma visão geral dos vencedores por idioma.
Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:
## Language Name, N bytes
onde N
está o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:
## Ruby, <s>104</s> <s>101</s> 96 bytes
Se você quiser incluir vários números no cabeçalho (por exemplo, porque sua pontuação é a soma de dois arquivos ou você deseja listar as penalidades do sinalizador de intérpretes separadamente), verifique se a pontuação real é o último número no cabeçalho:
## Perl, 43 + 2 (-p flag) = 45 bytes
Você também pode transformar o nome do idioma em um link que será exibido no snippet do placar de líderes:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes
fonte
Respostas:
GS2 ,
1210 bytesO código-fonte usa a codificação CP437 . Experimente online!
Execução de teste
Como funciona
fonte
Regex (.NET),
122113 bytesSupondo que a entrada e a saída estejam unárias, e a saída é obtida da correspondência principal da regex.
Repartição do regex:
^(?=((?=.*$(?<=^(\3+(.+.))(.*?(?>(.\4)?)))).)+(.*))
calcula π̅ (x) e captura o restante da sequência no grupo de captura 6 para afirmação na segunda parte..*$
define o ponteiro para o final da string para que tenhamos o número inteirox
em uma direção.(?<=^(\3+(.+.))(.*?(?>(.\4)?)))
corresponde da direita para a esquerda e verifica o número composto fazendo um loop de x a 0.(.*?(?>(.\4)?))
é uma "variável" que começa em 0 na primeira iteração e continua no número da iteração anterior e faz um loop até x. Como o menor número composto é 4,(.\4)?
nunca falha na correspondência se o grupo de captura 4 estiver disponível.^(\3+(.+.))
verifica o que é deixado pela "variável" acima (iex - "variable"
) se é um número composto.((?=.*(?=\6$)(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))).)+
calcula φ (π̅ (x)), limitando as operações da esquerda para a direita com(?=\6$)
..*(?=\6$)
define o ponteiro para a posição π̅ (x). Vamos denotar y = π̅ (x).(?<=(?!(.+.)\8*(?=\6$)(?<=^\8+))(.+?(?>\9?)))
corresponde da direita para a esquerda e verifica o prime relativo, fazendo um loop de (y - 1) a 0(.+?(?>\9?))
é uma "variável" que começa em 1 na primeira iteração e continua no número da iteração anterior e faz um loop até y(?!(.+.)\8*(?=\6$)(?<=^\8+))
corresponde da esquerda para a direita 1 e verifica se a "variável" ey são primos relativos.(.+.)\8*(?=\6$)
escolhe um divisor de "variável" maior que 1 e um efeito colateral é que temos o número inteiro y à esquerda.(?<=^\8+)
verifica se o divisor de "variável" também é o divisor de y.1 No .NET, o olhar à frente define a direção como LTR em vez de seguir a direção atual; look-behind define a direção para RTL em vez de inverter a direção.
Teste a regex em RegexStorm .
A revisão 2 descarta grupos não capturadores e usa grupos atômicos em vez de sintaxe condicional.
fonte
J,
1514 bytesEste é um verbo tácito e monádico. Experimente online com J.js .
Como funciona
fonte
Sério , 27 bytes
Sim, eu venci o CJam! Experimente online
Explicação (
a
refere-se ao topo da pilha,b
refere-se ao segundo da parte superior):Nota: desde a publicação desta resposta, adicionei as funções pi e phi ao Seriously. Aqui está uma resposta não competitiva com essas funções:
Explicação (alguns comandos são alterados para não se sobreporem a outros):
fonte
Julia,
5250 bytesIsso cria uma função sem nome que aceita e número inteiro e retorna um número inteiro. Para chamá-lo, dê um nome, por exemplo
f=x->...
.Ungolfed:
fonte
sum
vez decount
para salvar alguns caracteres. É um pouco frustrante, no entanto - a outra maneira de contar os números primossum(isprime,1:x)
é exatamente do mesmo tamanho queendof(primes(x))
.sum
falha em coleções vazias enquantocount
retorna 0. Portantosum
, não produzirá o resultado desejado parax<4
.Mathematica, 24 bytes
fonte
PhiNotPi@#&
: 11 bytes: PPitão, 14 bytes
Demonstração , Verificador
Nós calculamos compostos usando um filtro simples, pegamos seu tamanho e salvamos em
J
. Em seguida, pegamos o MDC deJ
cada número atéJ
e contamos quantos resultados são iguais a 1.fonte
Minkolang 0.11 , 12 bytes (NÃO competitivo)
Esta resposta NÃO é competitiva. Eu implementei pi e phi como integrados antes de postar a pergunta, o que me dá uma vantagem injusta. Eu publico isso apenas para aqueles que estão interessados no idioma.
Experimente aqui.
Explicação
fonte
CJam, 28 bytes
Experimente este violino no intérprete CJam ou verifique todos os casos de teste de uma só vez .
Como funciona
fonte
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
. Isso está certo?Python, 137
139fonte
range(n) if
e])) if
Retina , 48 bytes
Experimente online!
Explicação
Converter entrada para unário.
Conte números compostos não maiores que a entrada, contando com que frequência podemos corresponder a uma sequência que consiste em pelo menos duas repetições de um fator de pelo menos 2.
Converta para unário novamente.
Calcular φ contando de quantas posições não é possível encontrar um fator (de pelo menos 2) do sufixo dessa posição, que também é um fator do prefixo (se encontrarmos esse fator, isso
i <= n
compartilha um fator comn
portanto, não é coprime). O.
final garante que não contemos zero (para o qual não conseguimos encontrar um fator de pelo menos 2).fonte
Regex (.NET),
8886 bytesExperimente online! (Como um programa Retina.)
Usa a mesma E / S da resposta de n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̷̨̰́̀ĥ̷̳ , ou seja, entrada unária e corresponde a uma substring do comprimento do resultado.
Pode ser possível reduzir ainda mais isso, substituindo um ou ambos os grupos de balanceamento por referências futuras.
Alternativa na mesma contagem de bytes:
Existem também algumas alternativas para a primeira metade, por exemplo, usar um lookahead negativo em vez de positivo para os números de composição, ou usar um condicional também.
Explicação
Suponho que você tenha um entendimento básico dos grupos de balanceamento , mas, em resumo, os grupos de captura no .NET são pilhas (portanto, toda vez que você reutiliza o grupo de captura, a nova captura é colocada na parte superior) e
(?<-x>...)
exibe uma captura da pilhax
. Isso é muito útil para contar as coisas.fonte
PARI / GP, 27 bytes
fonte
Gelatina , não concorrente
7 bytes Esta resposta não é concorrente, pois usa um idioma que pós-data do desafio.
Como funciona
fonte
Oitava,
5251Edit: economizou 1 byte graças a Thomas Kwa
Explicação:
fonte
PARI / GP, 35 bytes
fonte
SageMath 26 bytes
Funciona bem mesmo para
n=0
en=1
, graças à implementação do Sage.fonte
Gelatina , 6 bytes
Experimente online!
Esta é uma colaboração entre caird coinheringahhing e Mr. Xcoder no chat
Explicação
fonte
Gaia , 5 bytes
Experimente online!
fonte
Ohm v2 , 7 bytes
Experimente online!
fonte
MATL , 9 bytes (não concorrente)
Essa resposta não é competitiva, pois o idioma pós-desafio.
Usa a versão (10.1.0) do idioma / compilador.
Experimente online!
Explicação
fonte
GAP, 33 bytes
Number(l,p)
conta quantos elementos del
satisfazemp
. Para compensar o fato de que 1 não é nem primo nem composto, preciso subtrair de n um a mais que o número de primos até n. Em vez de fazer-1
por dois bytes, inicio a lista com -2 em vez de 1 ou 2, adicionando mais um número que é considerado primo porIsPrime
apenas um byte extra.fonte
Python 3.5 - 130 bytes
Se não for aceitável passar a função como p (n, 0,0), então +3 bytes.
Isso tira proveito do fato de eu usar o teorema de Wilson para verificar se um número é composto e precisar chamar o módulo de matemática para a função fatorial. O Python 3.5 adicionou uma função gcd ao módulo de matemática.
O primeiro loop do código aumentará k em um se o número for composto e aumentará em 0 de outra maneira. (Embora o teorema de Wilson seja válido apenas para números inteiros maiores que 1, ele trata 1 como primo, portanto, podemos explorar isso).
O segundo loop passará pelo intervalo de número de compostos e incrementará g somente quando o valor de não pi e l forem co-primos.
g é então o número de valores menor ou igual ao número de números compostos menores ou iguais a n.
fonte
Python 3 + sympy ,
5958 bytes* -1 byte substituindo
compositepi(k)
pork+~primepi(k)
.Experimente online!
fonte
05AB1E ,
118 bytesExperimente online!
Isso pode não ser competitivo - não consigo descobrir quando 05AB1E foi criado.
Como funciona
fonte
Pyt , 6 bytes
Explicação:
Experimente online!
fonte
NARS APL, 38 bytes, 19 caracteres
13π é a função totiente e 2π é a função prime de contagem <= seu argumento. Teste
fonte
Adicionar ++ , 21 bytes
Experimente online!
Como funciona
R
þP
þ
P
bL
1_
dR
Þ%
bL
G
!!
Sim, eu realmente queria experimentar o novo LaTex
fonte