Um OEIS após o outro

95

A partir de 13/03/2018 16:45 UTC, o vencedor é a resposta # 345 , de Scrooble . Isso significa que o concurso terminou oficialmente, mas fique à vontade para continuar postando respostas, desde que sigam as regras.

Além disso, basta um rápido grito para os três principais respondedores em termos de número de respostas:

1. NieDzejkob - 41 respostas

2. KSmarts - 30 respostas

3. Hyper Neutrino - 26 respostas


Esta é uma pergunta de encadeamento de respostas que usa sequências do OEIS e a duração do envio anterior.

Esta pergunta de encadeamento de respostas funcionará da seguinte maneira:

  • Vou postar a primeira resposta. Todas as outras soluções devem resultar disso.
  • O próximo usuário (vamos chamá-los de userA) encontrará a sequência OEIS na qual seu número de índice (veja abaixo) é igual ao comprimento do meu código.
  • Usando a sequência, eles devem então codificar, em um idioma não utilizado , um programa que use um número inteiro como entrada, n e produza o enésimo número nessa sequência.
  • Em seguida, eles postam sua solução após a minha e um novo usuário (usuárioB) deve repetir a mesma coisa.

O ntermo th de uma sequência é o termo n vezes após o primeiro, trabalhando com o primeiro valor sendo o primeiro valor fornecido em sua página OEIS. Nesta questão, usaremos a indexação 0 para essas seqüências. Por exemplo, com A000242 e n = 3, o resultado correto seria 25 .

Contudo!

Este não é um , portanto, o código mais curto não importa. Mas o tamanho do seu código ainda tem impacto. Para evitar a duplicação de seqüências, seu número de bytes deve ser exclusivo . Isso significa que nenhum outro programa enviado aqui pode ter o mesmo comprimento em bytes que o seu.

Se não houver uma sequência para o comprimento da última postagem, a sequência da sua postagem será a menor sequência não utilizada. Isso significa que as seqüências usadas também precisam ser únicas e que a sequência não pode ser a mesma que o seu número de bytes.

Depois que uma resposta for postada e nenhuma resposta nova for postada por mais de uma semana, a resposta antes da última postada (aquela que não quebrou a cadeia) vencerá.

Entrada e saída

Aplicam-se regras genéricas de entrada e saída. A entrada deve ser um número inteiro ou uma representação de sequência de um número inteiro e a saída deve ser o valor correto na sequência.

Formatação

Como na maioria das respostas, formate sua resposta como esta

# N. language, length, [sequence](link)

`code`

[next sequence](link)

*anything else*

Regras

  • Você deve esperar pelo menos 1 hora antes de postar uma resposta, depois de postar.
  • Você não pode postar duas vezes (ou mais) seguidas.
  • O número do índice de uma sequência é o número após a Apeça e com os zeros à esquerda removidos (por exemplo, A000040o número do índice é 40)
  • Você pode assumir que nem a entrada nem a saída exigida estarão fora do intervalo numérico do seu idioma, mas não abuse disso escolhendo um idioma que possa usar apenas o número 1, por exemplo.
  • Se o tamanho do seu envio for maior que 65536 caracteres, forneça um link para uma maneira de acessar o código (pastebin por exemplo).
  • n nunca será maior que 1000 ou estará fora dos limites da sequência, simplesmente para impedir que discrepâncias de precisão impeçam a concorrência de um idioma.
  • A cada 150 respostas (válidas), o número de vezes que um idioma pode ser usado aumenta. Portanto, depois que 150 soluções forem publicadas, todos os idiomas poderão ser usados ​​duas vezes (com todas as respostas anteriores contando para isso). Por exemplo, quando 150 respostas foram postadas, o Python 3 pode ser usado duas vezes, mas devido ao fato de já ter sido usado uma vez, isso significa que só pode ser usado mais uma vez até que 300 respostas sejam postadas.
  • Por favor, seja útil e poste um link para a próxima sequência a ser usada. Isso não é obrigatório, mas é uma recomendação.
  • Versões diferentes de idiomas, por exemplo, Python 2 e Python 3 são idiomas diferentes . Como regra geral, se as duas versões diferentes estão disponíveis no Try It Online, são idiomas diferentes, mas lembre-se de que essa é uma regra geral e não uma resposta rígida.
  • Não é proibido, mas tente não copiar o código da página OEIS e tente resolvê-lo.
  • A codificação física é permitida apenas se a sequência for finita. Observe que a resposta que solicitou isso ( nº 40 ) é a exceção à regra. Algumas respostas no início do código rígido da cadeia, mas elas podem ser ignoradas, pois não adianta excluir a cadeia até, digamos, # 100.

Resposta em cadeia

caird coinheringaahing
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Dennis
Tudo bem se um programa precisar de uma precisão de ponto flutuante melhor para o tipo float/ interno double, a fim de produzir valores para valores maiores n?
precisa saber é o seguinte
1
@Giuseppe Não, como você está gerando os números, fazendo a matemática, em vez de apenas colocá-los em uma matriz / string
Caird coinheringaahing
2
@cairdcoinheringaahing Na minha opinião, isso codifica a constante gama. Não funciona "em teoria" para números maiores.
user202729
6
Sala de chat
user202729

Respostas:

4

345. brainfuck , 162 bytes, A000301

+<<,[>>[>]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]<[<]<-]>>[>]+<[-]++<[>[>>+>+<<<-]>>>[<<<+>>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>[-]>[<<+>>-]<<<<-]>>too golfy.

Experimente online!

Próxima sequência!

Isso leva como entrada o caractere com ponto de código n(pelas especificações de BF) e gera da mesma maneira. Para ver os números, sugiro usar o EsotericIDE de @ Timwi .

Explicação:

+<<,                                  Initialize the tape with the first two Fibonacci numbers. Take loop counter from input.
[                                     n times:
  >>[>]                                 Move to the end of the tape. 
  <<[>>+>+<<<-]>>>[<<<+>>>-]            Add fib(n-2)...
  <<[>+>+<<-]>>[<<+>>-]                 and fib(n-1). Store on the end of the tape.
  <[<]<-                                Move back to start of tape. Update loop counter.
]                                     End loop.
>>[>]+<[-]++<                         Delete the extra Fibonacci number and prepare for exponentiation. 
[                                     fib(n) times:
  >[>>+>+<<<-]>>>[<<<+>>>-]<<           Copy the base (2) to preserve it.
  [>[>+>+<<-]>>[<<+>>-]<<<-]            Multiply what started as a 1 by the base.
  >[-]>[<<+>>-]<<<<-                    Clean up and update loop counter.
]                                     End loop.
>>too golfy.                          Add some bytes, for all sequences <162 had been used. Print result. 

Como isso armazena todos os números de Fibonacci até o mais importante, haverá uma falha na entrada realmente grande em uma fita delimitada.

Isso pode ser reduzido significativamente se você codificar a base (2), mas a golfidade não é um problema.

Khuldraeseth na'Barya
fonte
Como a próxima resposta (# 346) quebrou a cadeia, sua resposta é a vencedora!
caird coinheringaahing
1
@cairdcoinheringaahing Obrigado por este desafio incrível. Entristece-me que acabe agora, mas, como todas as coisas boas do mundo, acabe. Agora, para golf esta desculpa por código, por agora é a primeira resposta que ninguém vai ver, e ele deve ser impressionantemente curta ...
Khuldraeseth na'Barya
@Scrooble você não pode realmente mudar o comprimento ...
NieDzejkob
@NieDzejkob Sim, mas eu posso jogar golfe e adicionar mais um pouco de preenchimento, para manter o mesmo comprimento.
Khuldraeseth na'Barya
@cairdcoinheringaahing "quebrou a cadeia"? O que isso significa?
Magic Octopus Urn
40

22. FiM ++ , 982 bytes, A000024

Nota : se você estiver lendo isso, convém classificar por "mais antigo".

Dear PPCG: I solved A000024!

I learned how to party to get a number using the number x and the number y.
Did you know that the number beers was x?
For every number chug from 1 to y,
  beers became beers times x!
That's what I did.
Then you get beers!
That's all about how to party.

Today I learned how to do math to get a number using the number n.
Did you know that the number answer was 0?
For every number x from 1 to n,
  For every number y from 1 to n,
    Did you know that the number tmp1 was how to party using x and 2?
    Did you know that the number tmp2 was how to party using y and 2?
    Did you know that the number max was how to party using 2 and n?
    tmp2 became tmp2 times 10!
    tmp1 became tmp1 plus tmp2!
    If tmp1 is more than max then: answer got one more.
  That's what I did.
That's what I did.
Then you get answer!
That's all about how to do math.

Your faithful student, BlackCap.

PS:  This is the best answer
PPS: This really is the best answer

Próxima sequência

BlackCap
fonte
10
Hahaha, riu tanto com a coisa toda. +1 para a escolha do idioma :-)
ETHproductions
Incrível,
aceite
22

1. Triangular , 10 bytes, A000217

$\:_%i/2*<

Experimente online!

Próxima sequência

Como funciona

O código formata esse triângulo

   $
  \ :
 _ % i
/ 2 * <

com o IP iniciando no $e movendo-se para o sudeste (SE, heh), funciona assim:

$            Take a numerical input (n);     STACK = [n]
 :           Duplicate it;                   STACK = [n, n]
  i          Increment the ToS;              STACK = [n, n+1]
   <         Set IP to W;                    STACK = [n, n+1]
    *        Multiply ToS and 2ndTos;        STACK = [n(n+1)]
     2       Push 2;                         STACK = [n(n+1), 2]
      /      Set IP to NE;                   STACK = [n(n+1), 2]
       _     Divide ToS by 2ndToS;           STACK = [n(n+1)/2]
        \    Set IP to SE (heh);             STACK = [n(n+1)/2]
         %   Output ToS as number;           STACK = [n(n+1)/2]
          *  Multiply ToS by 2ndToS (no op); STACK = [n(n+1)/2]
caird coinheringaahing
fonte
13
1. Triangular, 10 bytes, A000217. * segue link * A000217 Triangular numbers...
MD XF
22

73. Estrelado , 363 bytes, A000252

, +      + *     '.     `
 + + + +  *  *  *  +     
 +`      +*       +    ` 
 + +   +  + +   + *  '   
   +   '  ####`  + +   + 
 + +    ####  +*   +    *
    '  #####  +      + ' 
  `    ######+  + +   +  
+ +   + #########   * '  
 +   +  + #####+ +      +
*  +      + * +  *  *   +
   +  *  + + + +  *  *   
+   +  +   *   + `  + +  
 +  + +   + *'    +    +.

Experimente online!

Próxima sequência

Usa a fórmula " a(n) = n^4 * product p^(-3)(p^2 - 1)*(p - 1)onde o produto está sobre todos os números primos p que dividem n" do OEIS.

A lua não funciona, mas, ei, isso não é golfe de código.

Não é uma árvore
fonte
estrelas na lua? hmmm
betseg 01/01
19

97. Python 3 (PyPy) , 1772 bytes, A000236

Antes de tudo, muito obrigado ao Dr. Max Alekseyev por ser paciente comigo. Tenho muita sorte de poder entrar em contato com ele por e-mail para entender esse desafio. Sua resposta Math.SE aqui me ajudou muito. Agradeço ao Wheat Wizard por me ajudar também. :)

plist = []

def primes(maximal = -1): # Semi-efficient prime number generator with caching up to a certain max.
	index = plist and plist[-1] or 2
	for prime in plist:
		if prime <= maximal or maximal == -1: yield prime
		else: break
	while index <= maximal or maximal == -1:
		composite = False
		for prime in plist:
			if index % prime == 0:
				composite = True
				break
		if not composite:
			yield index
			plist.append(index)
		index += 1

def modinv(num, mod): # Multiplicative inverse with a modulus
	index = 1
	while num * index % mod != 1: index += 1
	return index

def moddiv(num, dnm, mod):
	return num * modinv(dnm, mod) % mod

def isPowerResidue(num, exp, mod):
	for base in range(mod):
		if pow(base, exp, mod) == num:
			return base
	return False

def compute(power, prime):
	for num in range(2, prime):
		if isPowerResidue(moddiv(num - 1, num, prime), power, prime):
			return num - 1
	return -1

# file = open('output.txt', 'w')

def output(string):
	print(string)
	# file.write(str(string) + '\n')

def compPrimes(power, count):
	maximum = 0
	index = 0
	for prime in getValidPrimes(power, count):
		result = compute(power, prime)
		if result > maximum: maximum = result
		index += 1
		# output('Computed %d / %d = %d%% [result = %d, prime = %d]' % (index, count, (100 * index) // count, result, prime))
	return maximum

def isValidPrime(power, prime):
	return (prime - 1) % power == 0

def getValidPrimes(power, count):
	collected = []
	for prime in primes():
		if isValidPrime(power, prime):
			collected.append(prime)
		if len(collected) >= count:
			return collected
		# output('Collected %d / %d = %d%% [%d]' % (len(collected), count, (100 * len(collected)) // count, prime))

power = int(input()) + 2

output(compPrimes(power, 100))

# file.close()

Experimente online!

Se der o resultado errado, basta aumentar 100 para algo maior. Eu acho que 10000 funcionará para 4, mas deixarei meu computador funcionando durante a noite para confirmar isso; pode demorar algumas horas para terminar.

Observe que a parte (PyPy) é apenas para que eu possa usar o Python novamente. Realmente não conheço muitas outras linguagens e não vou tentar portar isso para Java e arriscar não terminar a tempo.

Próxima sequência (também não faça mais coisas matemáticas malucas; não tenho mais versões em Python, para que alguém tenha que salvar esse desafio D :)

HyperNeutrino
fonte
bem há sempre pypy3
ASCII-only
15

107. TrumpScript , 1589 bytes, A000047

My cat hears everything really well
because with me every cat is a safe cat
Everybody knows that one is 1000001 minus 1000000
but only most of you that two is, one plus one;
As always nothing is, one minus one;
My dog is one year old.
I promise you that as long as you vote on me, nothing will be less cool than a cat;:
Much dog is, dog times two;
Dead cat is, cat minus one;!
I will make dog feel good, food for dog plus one;
Roads can be made using different things. Asphalt is one of them.
As long as Hillary jailed, I love asphalt less than my dog;:
Roads are, always made using asphalt plus one of other things;
I promise my roadways are, two times asphalt than you want;
My roadways are great, always roadways plus one;
Vladimir is nothing more than my friend.
Name of Putin is Vladimir.
As long as, Putin eat less roadways;:
China is nothing interesting.
We all know people speaking Chinese are from China.
As long as, Chinese makes less roads;:
I will make economy, for Putin - Chinese will love me;
If it will mean, economy is asphalt in Russia?;:
I will make cat feel good, cat plus one dollar on food;
Make Vladimir roadways to help Russia economy.
Never make china roads!
I show you how great China is, China plus one; You can add numbers to China.
Like Chinese is, China times China makes sense;
Like Chinese is, two times Chinese letter;!
Make Vladimir happy, Vladimir plus one million dollars;
I also show you how great Putin is, Vladimir times Vladimir; You can do number stuff to Putin too!
I will make asphalt roads a lot!
Everybody say cat. You did it? America is great.

Experimente online!

Na primeira programação em TrumpScript, é possível que eu tenha reinventado a roda algumas vezes - 4 linhas são dedicadas ao cálculo de 2 ^ n. Tentei fazer parecer algo que Trump (bêbado) poderia dizer. Como bônus, aqui está um script Python que escrevi para verificar se estou fazendo tudo certo. Existem algumas diferenças no programa acima, mas grande parte é diretamente equivalente.

cat = int(input())
dog = 2 ** cat + 1
asphalt = 1
cat = 0
while asphalt < dog:
    roads = asphalt + 1
    roadways = 2 * asphalt + 1
    vladimir = 0
    putin = vladimir
    while putin < roadways:
        china = 0
        chinese = china
        while chinese < roads:
            chair = putin - chinese
            if chair == asphalt:
                cat += 1
                vladimir = roadways
                china = roads
            china += 1
            chinese = 2 * china * china
        vladimir += 1
        putin = vladimir * vladimir
    asphalt = roads
print(cat)

Próxima sequência!

NieDzejkob
fonte
3
I will make cat feel goodO_O
Business Cat
Infelizmente I will make Business Cat feel goodnão vai funcionar ...
NieDzejkob
14

30. Python 1 , 1112 bytes, A000046

def rotations(array):
	rotations = []
	for divider_index in range(len(array)):
		rotations.append(array[divider_index:] + array[:divider_index])
	return rotations

def next(array):
	for index in range(len(array) - 1, -1, -1):
		array[index] = 1 - array[index]
		if array[index]: break
	return array

def reverse(array):
	reversed = []
	for index in range(len(array) - 1, -1, -1):
		reversed.append(array[index])
	return reversed

def primitive(array):
	for index in range(1, len(array)):
		if array == array[:index] * (len(array) / index): return 1
	return 0

def necklaces(size):
	previous_necklaces = []
	array = [0] * size
	necklaces = 0
	for iteration in range(2 ** size):
		if not primitive(array) and array not in previous_necklaces:
			necklaces = necklaces + 1
			for rotation in rotations(array):
				complement = []
				for element in rotation:
					complement.append(1 - element)
				previous_necklaces.append(rotation)
				previous_necklaces.append(complement)
				previous_necklaces.append(reverse(rotation))
				previous_necklaces.append(reverse(complement))
		array = next(array)
	return necklaces

Experimente online!

Nem vai se incomodar em jogar isso. Ei, não é a minha resposta mais longa em Python neste site!

Próxima sequência

HyperNeutrino
fonte
1
Parabéns por decodificar a matemática: D
Leaky Nun
2
313 bytes, lol #
Leaky Nun
@LeakyNun Como eu estava dizendo, eu não me incomodei em jogar esse lol. Além disso, não é a minha resposta Python mais longo neste local tão IDC: P mas agradável
HyperNeutrino
@LeakyNun E graças: D Levei um tempo para entender tudo isso lol
HyperNeutrino
@LeakyNun 309 bytes porque o valor real de _é irrelevante; só precisamos repetir isso muitas vezes
HyperNeutrino
13

2. Haskell, 44 bytes, A000010

f k|n<-k+1=length.filter(==1)$gcd n<$>[1..n]

Experimente online!

Próxima sequência

BlackCap
fonte
12
O nome da próxima sequência embora ...
totallyhuman
coelhos pobres @totallyhuman ...
Erik as Outgolfer
Devemos vincular ao post anterior?
Leaky Nun
Dói-me que não posso jogar golfe agora. Eu tive que ser o primeiro a ver
BlackCap
Qual é a próxima sequência? Eu não entendo os três: P
Decaimento beta
13

9. Pyth , 19 bytes, A000025

?>Q0sm@_B1-edld./Q1

Conjunto de teste .

Próxima sequência

a (n) = número de partições de n com classificação par menos número com classificação ímpar. A classificação de uma partição é a maior parte menos o número de partes.

Freira Furada
fonte
Para quem conhece Pyth, usei deliberadamente em >Q0vez de Q, a fim de, você sabe, ter a próxima sequência como A000019.
Leaky Nun
1
Da página OEISKeywords: easy,nice
BlackCap
@LeakyNun Sim, pois caso contrário eu teria que resolver A000017 ... nojento.
Erik the Outgolfer
12

8. Mathematica (10.1), 25 bytes, A000070

Tr@PartitionsP@Range@#+1&

Próxima sequência

LegionMammal978
fonte
A sequência perfeita para usar o Mathematica.
Leaky Nun
1
A000025 é incrivelmente difícil. Você deve adicionar um byte para obter A000026. : P
MD XF
12

206. Próton , 3275 bytes, A000109

# This took me quite a while to write; if it's wrong, please tell me and I'll try to fix it without changing the byte count..

permutations = x => {
	if len(x) == 0 return [ ]
	if len(x) == 1 return [x]
	result = []
	for index : range(len(x)) {
		for permutation : permutations(x[to index] + x[index + 1 to]) {
			result.append([x[index]] + permutation)
		}
	}
	return result
}

adjacency = cycles => {
	cycles = cycles[to]
	size = cycles.pop()
	matrix = [[0] * size for i : range(size)]
	for cycle : cycles {
		i, j, k = cycle[0], cycle[1], cycle[2]
		matrix[i][j] = matrix[i][k] = matrix[j][i] = matrix[j][k] = matrix[k][i] = matrix[k][j] = 1
	}
	return matrix
}

transform = a => [[a[j][i] for j : range(len(a[i]))] for i : range(len(a))]

isomorphic = (a, b) => {
	return any(sorted(b) == sorted(transform(A)) for A : permutations(transform(a)))
}

intersection = (a, b) => [x for x : a if x in b]

union = (a, b) => [x for x : a if x not in b] + list(b)

validate = graph => {
	matrix = adjacency(graph)
	rowsums = map(sum, matrix)
	r = 0
	for s : rowsums if s + 1 < graph[-1] r++
	return 2 || r
}

graphs = nodes => {
	if nodes <= 2 return []
	if nodes == 3 return [[(0, 1, 2), 3]]
	result = []
	existing = []
	for graph : graphs(nodes - 1) {
		graph = graph[to]
		next = graph.pop()
		for index : range(len(graph)) {
			g = graph[to]
			cycle = g.pop(index)
			n = g + [(cycle[0], cycle[1], next), (cycle[1], cycle[2], next), (cycle[2], cycle[0], next), next + 1]
			N = sorted(adjacency(n))
			if N not in existing {
				existing += [sorted(transform(a)) for a : permutations(transform(adjacency(n)))]
				result.append(n)
			}
			for secondary : index .. len(graph) - 1 {
				g = graph[to]
				c1 = g.pop(index)
				c2 = g.pop(secondary)
				q = union(c1, c2)
				g = [k for k : g if len(intersection(k, intersection(c1, c2))) <= 1]
				if len(intersection(c1, c2)) == 2 {
					for i : range(3) {
						for j : i + 1 .. 4 {
							if len(intersection(q[i, j], intersection(c1, c2))) <= 1 {
								g.append((q[i], q[j], next))
							}
						}
					}
				}
				g.append(next + 1)
				N = sorted(adjacency(g))
				if N not in existing {
					existing += [sorted(transform(a)) for a : permutations(transform(adjacency(g)))]
					result.append(g)
				}
				for tertiary : secondary .. len(graph) - 2 {
					g = graph[to]
					c1 = g.pop(index)
					c2 = g.pop(secondary)
					c3 = g.pop(tertiary)
					q = union(union(c1, c2), c3)
					g = [k for k : g if len(intersection(k, intersection(c1, c2))) <= 1 and len(intersection(k, intersection(c2, c3))) <= 1]
					if len(q) == 5 and len(intersection((q1 = intersection(c1, c2)), (q2 = intersection(c2, c3)))) <= 1 and len(q1) == 2 and len(q2) == 2 {
						for i : range(4) {
							for j : i + 1 .. 5 {
								if len(intersection(q[i, j], q1)) <= 1 and len(intersection(q[i, j], q2)) <= 1 {
									g.append((q[i], q[j], next))
								}
							}
						}
						g.append(next + 1)
						N = sorted(adjacency(g))
						if N not in existing {
							existing += [sorted(transform(a)) for a : permutations(transform(adjacency(g)))]
							result.append(g)
						}
					}
				}
			}
		}
	}
	return [k for k : result if max(sum(k[to -1], tuple([]))) + 1 == k[-1] and validate(k)]
}

x = graphs(int(input()) + 3)
print(len(x))

Experimente online!

Próxima sequência

HyperNeutrino
fonte
Espere, você realmente fez isso? Se você não escreve um artigo com esses programas e vai conversar com algum professor, está deixando passar algo interessante: P
Stephen
@Stephen Atualmente correções de bugs lol
HyperNeutrino 10/10
Essa é a abordagem de dividir triângulos, quadrados e pentágonos conforme plantri? Parece que pode ser, mas parte da sintaxe é desconhecida.
Peter Taylor
1
@PeterTaylor Supondo que eu entenda a abordagem que você está descrevendo, sim, ele procura triângulos e coloca um vértice adjacente aos 3 vértices ou dois ciclos adjacentes e exclui a aresta comum e coloca um vértice adjacente aos 4, o mesmo para 3 triângulos em um pentágono. Eu acho que você está descrevendo.
HyperNeutrino
1
@ CristianSievers math.stackexchange.com/a/2463430/457091
HyperNeutrino
12

308. ENIAC (simulador) , 3025 bytes, A006060

Pseudo-código:

repeat{
    M←input
    N←-M
    A←1
    B←253
    while(N<0){
        C←60
        C←C-A
        repeat(194){
            C←C+B
        }
        A←B
        B←C
        N←N+1
    }
    output←A
}

Sem simulador online, resultado da execução: Entrada do leitor de cartão Saída do cartão perfurado

Registradores e constantes:

A: 1-2
B: 3-4
C: 5-6
M: 7
N: 8

input: const. A
253: const. J
60: const. K
194: Master programmer decade limit 1B

Programe fluxo de sinal e fluxo de dados: Programe fluxo de sinal e fluxograma de dados

"Código" completo no pastebin ou nos comentários HTML na marcação desta resposta, para impedir que o linkrot e uma resposta bastante longa percorram ao mesmo tempo. Isto é divertido!

Próxima sequência

leo3065
fonte
Você pode adicionar um link para a próxima sequência, por favor
Zachary
@ Zacharý O link está no post. Vou movê-lo para o final da postagem, para que seja mais fácil encontrá-lo.
Leo3065
12

15. CJam, 85 bytes, A000060

{ee\f{\~\0a*@+f*}:.+}:C;2,qi:Q,2f+{_ee1>{~2*\,:!X*X<a*~}%{CX<}*W=+}fX_0a*1$_C.- .+Q)=

Demonstração online

Próxima sequência

Dissecação

OEIS dá

Gf: S (x) + S (x ^ 2) -S (x) ^ 2, em que S (x) é a função geradora para A000151. - Pab Ter, 12 de outubro de 2005

Onde

S(x)=xEu11(1-xEu)2s(Eu)=xEu1(1+xEu+x2Eu+...)2s(Eu)
{           e# Define a block to convolve two sequences (multiply two polynomials)
  ee\f{     e#   Index one and use the other as an extra parameter for a map
    \~\0a*  e#     Stack manipulations; create a sequence of `index` 0s
    @+f*    e#     Shift the extra parameter poly and multiply by the coefficient
  }
  :.+       e#   Fold pointwise add to sum the polys
}:C;        e# Assign the block to C (for "convolve")
2,          e# Initial values of S: S(0) = 0, S(1) = 1
qi:Q        e# Read integer and assign it to Q
,2f+{       e# For X = 2 to Q+1
  _ee1>     e#   Duplicate accumulator of S, index, and ditch 0th term
  {         e#   Map (over notional variable i)
    ~2*\    e#     Double S(i) and flip i to top of stack
    ,:!     e#     Create an array with a 1 and i-1 0s
    X*X<    e#     Replicate X times and truncate to X values
            e#     This gives g.f. 1/(1-x^i) to the first X terms
    a*~     e#     Create 2S(i) copies of this polynomial
  }%
  {CX<}*    e#   Fold convolution and truncation to X terms
  W=+       e#   Append the final coefficient, which is S(X), to the accumulator
}fX
_0a*        e# Pad a copy to get S(X^2)
1$_C        e# Convolve two copies to get S(X)^2
.-          e# Pointwise subtraction
 .+         e# Pointwise addition. Note the leading space because the parser thinks
            e# -. is an invalid number
Q)=         e# Take the term at index Q+1 (where the +1 adjusts for OEIS offset)
Peter Taylor
fonte
1 minuto e 33 segundos à frente de mim ... enquanto eu estava escrevendo a explicação
Leaky Nun
11

67. LOLCODE , 837 bytes, A000043

HAI 1.2
  CAN HAS STDIO?

  I HAS A CONT ITZ 0
  I HAS A ITRZ ITZ 1
  I HAS A NUMBAH
  GIMMEH NUMBAH
  NUMBAH R SUM OF NUMBAH AN 1

  IM IN YR GF
    ITRZ R SUM OF ITRZ AN 1

    I HAS A PROD ITZ 1
    IM IN YR MOM UPPIN YR ASS WILE DIFFRINT ITRZ AN SMALLR OF ITRZ AN ASS
      PROD R PRODUKT OF PROD AN 2
    IM OUTTA YR MOM
    PROD R DIFF OF PROD AN 1

    I HAS A PRAIME ITZ WIN
    I HAS A VAR ITZ 1
    IM IN YR MOM
      VAR R SUM OF VAR AN 1
      BOTH SAEM VAR AN PROD, O RLY?
        YA RLY, GTFO
      OIC
      BOTH SAEM 0 AN MOD OF PROD AN VAR, O RLY?
        YA RLY
          PRAIME R FAIL
          GTFO
      OIC
    IM OUTTA YR MOM

    BOTH SAEM PRAIME AN WIN, O RLY?
      YA RLY, CONT R SUM OF CONT AN 1
    OIC

    BOTH SAEM NUMBAH AN CONT, O RLY?
      YA RLY, GTFO
    OIC
  IM OUTTA YR GF

  VISIBLE ITRZ
KTHXBYE

Minha tecla capslock está fadada a escapar, então eu escrevi essa coisa toda enquanto pressionava shift.

Experimente online!

Próxima sequência

BlackCap
fonte
+1 para usarPRAIME
Leaky Nun
3
Você é um programador, poderia escrever isso e executá-lo através de um script Python que upperd-it-.
Stephen
5
@StepHen Ou simplesmente gggUGno vim onde eu escrevi isso, mas eu não sou tão inteligente
Cabeção
10

10. Magma, 65 bytes, A000019

f:=function(n);return NumberOfPrimitiveGroups(n+1);end function;

Experimente aqui

lol builtin

Próxima sequência

HyperNeutrino
fonte
@ETHproductions :) nenhum problema, graças a página OEIS embora porque ele tem o builtin exata lá lol
HyperNeutrino
4
; _; Eu resolvi o A000064 e você o mudou. Votado.
Leaky Nun
Meu Deus, tantas seqüências de partição
ETHproductions
Resolvi acidentalmente o A007317 ao tentar fazer isso em Python ( TIO ): P
ETHproductions
Re-votado! \ o /
Leaky Nun
9

121. Pip , 525 bytes, A000022

n:(a+1)//2
t:[[0]RL(3*a+3)PE1]
Fh,n{
  m:([0]RL(3*a+3))
  Fi,(a+1){
    Fj,(a+1){
      Fk,(a+1)m@(i+j+k)+:(t@h@i)*(t@h@j)*(t@h@k)
      m@(i+2*j)+:3*(t@h@i)*(t@h@j)
    }
    m@(3*i)+:2*(t@h@i)
  }
  t:(tAE(m//6PE1))
}
k:t@n
o:0
Fh,aFi,aFj,aI(h+i+j<a)o+:(k@h)*(k@i)*(k@j)*k@(a-1-h-i-j)
Fh,((a+1)//2){
  Fi,aI(2*h+i<a){o+:6*(k@h)*(k@i)*(k@(a-1-2*h-i))}
  I(a%2=1)o+:3*(k@h)*(k@((a-1-2*h)//2))
}
Fh,((a+2)//3)o+:8*(k@h)*(k@(a-1-3*h))
I(a%4=1)o+:6*k@(a//4)
o//:24
Ia(o+:t@n@a)
Fh,nFj,(a+1)o-:(t@(h+1)@j-t@h@j)*(t@(h+1)@(a-j))
o

Demonstração online

Próxima sequência

Curiosidade: quando o desafio foi lançado pela primeira vez, elaborei uma lista de pequenos números de sequência desagradáveis ​​que desejava apontar com o CJam e o A000022 estava no topo da lista.

Isso implementa a função geradora descrita em EM Rains e NJA Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees) , Journal of Integer Sequences, vol. 2 (1999), levando a soma para tantos termos quanto necessário para que o coeficiente fosse fixado e depois telescopando três quartos da soma. Em particular, telescopar a primeira metade significa que o índice de ciclo apenas deve ser aplicado a uma delas e não a todas elas.CknS4Th

O código é dividido como

; Calculate the relevant T_h
t:[[0]RL(3*a+3)PE1]
Fh,n{
  m:([0]RL(3*a+3))
  Fi,(a+1){
    Fj,(a+1){
      Fk,(a+1)m@(i+j+k)+:(t@h@i)*(t@h@j)*(t@h@k)
      m@(i+2*j)+:3*(t@h@i)*(t@h@j)
    }
    m@(3*i)+:2*(t@h@i)
  }
  t:(tAE(m//6PE1))
}

; Calculate the cycle index of S_4 applied to the last one
k:t@n
o:0
Fh,aFi,aFj,aI(h+i+j<a)o+:(k@h)*(k@i)*(k@j)*k@(a-1-h-i-j)
Fh,((a+1)//2){
  Fi,aI(2*h+i<a){o+:6*(k@h)*(k@i)*(k@(a-1-2*h-i))}
  I(a%2=1)o+:3*(k@h)*(k@((a-1-2*h)//2))
}
Fh,((a+2)//3)o+:8*(k@h)*(k@(a-1-3*h))
I(a%4=1)o+:6*k@(a//4)
o//:24

; Handle the remaining convolution,
; pulling out the special case which involves T_{-2}
Ia(o+:t@n@a)
Fh,nFj,(a+1)o-:(t@(h+1)@j-t@h@j)*(t@(h+1)@(a-j))

Note que este é o meu primeiro programa Pip, então provavelmente não é muito idiomático.

Peter Taylor
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Dennis
9

156. C # (Mono), 2466 bytes, A000083

Nota: a pontuação é 2439 bytes para o código e 27 para o sinalizador do compilador -reference:System.Numerics.

using Num = System.Numerics.BigInteger;
namespace PPCG
{
    class A000083
    {
        static void Main(string[] a)
        {
            int N = int.Parse(a[0]) + 1;

            var phi = new int[N + 1];
            for (int i = 1; i <= N; i++)
                phi[i] = 1;
            for (int p = 2; p <= N; p++)
            {
                if (phi[p] > 1) continue;
                for (int i = p; i <= N; i += p)
                    phi[i] *= p - 1;
                int pa = p * p;
                while (pa <= N)
                {
                    for (int i = pa; i <= N; i += pa)
                        phi[i] *= p;
                    pa *= p;
                }
            }

            var aik = new Num[N + 1, N + 1];
            var a035350 = new Num[N + 1];
            var a035349 = new Num[N + 1];
            aik[0, 0] = aik[1, 1] = a035350[0] = a035350[1] = a035349[0] = a035349[1] = 1;
            for (int n = 2; n <= N; n++)
            {
                // A000237 = EULER(A035350)
                Num nbn = 0;
                for (int k = 1; k < n; k++)
                    for (int d = 1; d <= k; d++)
                        if (k % d == 0) nbn += d * a035350[d] * aik[1, n - k];
                aik[1, n] = nbn / (n - 1);

                // Powers of A000237 are used a lot
                for (int k = 2; k <= N; k++)
                    for (int i = 0; i <= n; i++)
                        aik[k, n] += aik[k - 1, i] * aik[1, n - i];

                // A035350 = BIK(A000237)
                Num bn = 0;
                for (int k = 1; k <= n; k++)
                {
                    bn += aik[k, n];
                    if (k % 2 == 1)
                        for (int i = n & 1; i <= n; i += 2)
                            bn += aik[1, i] * aik[k / 2, (n - i) / 2];
                    else if (n % 2 == 0)
                        bn += aik[k / 2, n / 2];
                }
                a035350[n] = bn / 2;

                // A035349 = DIK(A000237)
                Num dn = 0;
                for (int k = 1; k <= n; k++)
                {
                    // DIK_k is Polyà enumeration with the cyclic group D_k
                    // The cycle index for D_k has two parts: C_k and what Bower calls CPAL_k
                    // C_k
                    Num cikk = 0;
                    for (int d = 1; d <= k; d++)
                        if (k % d == 0 && n % d == 0)
                            cikk += phi[d] * aik[k / d, n / d];
                    dn += cikk / k;

                    // CPAL_k
                    if (k % 2 == 1)
                        for (int i = 0; i <= n; i += 2)
                            dn += aik[1, n - i] * aik[k / 2, i / 2];
                    else
                    {
                        Num cpalk = 0;
                        for (int i = 0; i <= n; i += 2)
                            cpalk += aik[2, n - i] * aik[k / 2 - 1, i / 2];
                        if (n % 2 == 0)
                            cpalk += aik[k / 2, n / 2];
                        dn += cpalk / 2;
                    }
                }
                a035349[n] = dn / 2;
            }

            // A000083 = A000237 + A035350 - A000237 * A035349
            var a000083 = new Num[N + 1];
            for (int i = 0; i <= N; i++)
            {
                a000083[i] = aik[1, i] + a035349[i];
                for (int j = 0; j <= i; j++) a000083[i] -= aik[1, j] * a035350[i - j];
            }

            System.Console.WriteLine(a000083[N - 1]);
        }
    }
}

Demonstração online . Este é um programa completo que recebe informações da linha de comando.

Próxima sequência

Dissecação

Sigo o comentário de Bowen no OEIS de que a função geradora em A000083(x) = A000237(x) + A035349(x) - A000237(x) * A035350(x)que o componente gerador de funções está relacionada por transformações como

  • A000237(x) = x EULER(A035350(x))
  • A035350(x) = BIK(A000237(x))
  • A035349(x) = DIK(A000237(x))

Uso as definições de BIKe DIKde https://oeis.org/transforms2.html, mas as fórmulas parecem ter vários erros de digitação. Corrigi LPALsem muita dificuldade e derivou independentemente uma fórmula DIKbaseada na aplicação da enumeração de Pólya ao índice de ciclo do grupo diédrico . Entre os números 121 e 156, estou aprendendo muito sobre a enumeração de Pólya. Enviei algumas erratas , que podem ser úteis para outras pessoas se essas transformações surgirem novamente na cadeia.

Peter Taylor
fonte
8

13. VB.NET (.NET 4.5), 1246 bytes, A000131

Public Class A000131
    Public Shared Function Catalan(n As Long) As Long
        Dim ans As Decimal = 1
        For k As Integer = 2 To n
            ans *= (n + k) / k
        Next
        Return ans
    End Function
    Shared Function Answer(n As Long) As Long

        n += 7

        Dim a As Long = Catalan(n - 2)

        Dim b As Long = Catalan(n / 2 - 1)
        If n Mod 2 = 0 Then
            b = Catalan(n / 2 - 1)
        Else
            b = 0
        End If

        Dim c As Long = Catalan(n \ 2 - 1) ' integer division (floor)

        Dim d As Long
        If n Mod 3 = 0 Then
            d = Catalan(n / 3 - 1)
        Else
            d = 0
        End If

        Dim e As Long = Catalan(n / 4 - 1)
        If n Mod 4 = 0 Then
            e = Catalan(n / 4 - 1)
        Else
            e = 0
        End If

        Dim f As Long = Catalan(n / 6 - 1)
        If n Mod 6 = 0 Then
            f = Catalan(n / 6 - 1)
        Else
            f = 0
        End If

        Return (
                    a -
                    (n / 2) * b -
                    n * c -
                    (n / 3) * d +
                    n * e +
                    n * f
                ) /
                (2 * n)
    End Function
End Class

A001246

Experimente Online!

Brian J
fonte
8

91. Python 2 (PyPy) , 1733 bytes, A000066

import itertools

girth = int(input()) + 3

v = 4

r = range

def p(v):
	a = [0 for i in r(v)]
	k = int((v * 2) ** .5)
	a[k - 1] = a[k - 2] = a[k - 3] = 1
	j = len(a) - 1
	for i in r(1, 3):
		a[j] = 1
		j -= i
	yield [x for x in a]
	while not all(a):
		for index in r(len(a) - 1, -1, -1):
			a[index] ^= 1
			if a[index]: break
		yield [x for x in a]

def wrap_(p, v):
	m = [[0 for j in r(v)] for i in r(v)]
	k = 0
	for i in r(0, v - 1):
		for j in r(i + 1, v):
			m[i][j] = m[j][i] = p[k]
			k += 1
	return m

def completes_cycle(edgelist):
	if not edgelist or not edgelist[1:]: return False
	start = edgelist[0]
	edge = edgelist[0]
	e = [x for x in edgelist]
	edgelist = edgelist[1:]
	while edgelist:
		_edges = [_edge for _edge in edgelist if _edge[0] in edge or _edge[1] in edge]
		if _edges:
			edgelist.remove(_edges[0])
			if _edges[0][1] in edge: _edges[0] = (_edges[0][1], _edges[0][0])
			edge = _edges[0]
		else:
			return False
	flat = sum(e, ())
	for i in flat:
		if flat.count(i) != 2: return False
	return edge[1] in start

def powerset(a):
	return sum([list(itertools.combinations(a, t)) for t in r(len(a))], [])

while True:
	ps = (v * (v - 1)) // 2
	skip = False
	for Q in p(ps):
		m = wrap_(Q, v)
		output = [row + [0] for row in m]
		output.append([0 for i in r(len(m[0]))])
		for i in r(len(m)):
			output[i][-1] = sum(m[i])
			output[-1][i] = sum(row[i] for row in m)
		if all(map(lambda x: x == 3, map(sum, m))):
			edges = []
			for i in r(v):
				for j in r(i, v):
					if m[i][j]: edges.append((i, j))
			for edgegroup in powerset(edges):
				if completes_cycle(list(edgegroup)):
					if len(edgegroup) == girth:
						print(v)
						exit(0)
					else:
						skip = True
						break
		if skip: break
	v += 1

Experimente online!

Espero que o uso do Python 2 PyPy conte como outra versão principal. Se alguém pudesse me conseguir um intérprete Python 0, eu também poderia usá-lo, mas espero que isso seja válido.

Isso começa em 1 vértice e funciona, criando a representação da matriz de adjacência de todos os possíveis grafos não direcionados com tantos vértices. Se for trivalente, ele examinará o conjunto de potências das arestas, que serão classificadas por comprimento. Se o primeiro ciclo encontrado for muito curto, ele seguirá em frente. Se o primeiro ciclo encontrado corresponder à entrada (deslocamento de 3), ele produzirá a contagem correta de vértices e terminará.

Próxima sequência <- tenha uma fácil como uma pausa de toda essa bobagem matemática: D

EDIT : Adicionei algumas otimizações para torná-lo um pouco mais rápido (ainda não é possível calcular o terceiro período dentro do limite de 60 segundos do TIO) sem alterar o número de bytes.

HyperNeutrino
fonte
... e eu estava pensando seriamente que a cadeia terminaria com a resposta 90
pppery
1
@ppperry :) Eu gosto de fazer desafios difíceis porque a maioria das pessoas não pode sequer fazer uma solução para que eu não precisa se preocupar em ficar outgolfed :) (por exemplo, o problema da cadeia namer carbono)
HyperNeutrino
A menos que alguém toma a sua solução e converte-lo em uma linguagem terser
pppery
@ppperry that too o_O: P
HyperNeutrino
1
@HyperNeutrino Parabéns por resolver isso! Eu estava preocupado que tivesse quebrado a corrente e estava considerando preencher a contagem de bytes para apontar para uma sequência diferente. Bom trabalho!
22826 Scott Milner
8

232. Funky , 326 330 332 bytes, A000938

function gcd (a, b) {
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    };
    return a;
}

function A000938 (n) {
    n = n + 2;
    ans = 0;
    for (m = 2; m <= n; ++m) {
        for (k = 2; k <= n; ++k) {
            ans = ans + (((n - k) + 1) * ((n - m) + 1) * gcd(k - 1, m - 1));
        }
    }
    ans = (2 * ans) - (
        (n*n) *
        ((n*n)-1) / 6
    );
    return ans;
}

Experimente online!

Poliglota com Javascript. Experimente online!

Próxima sequência .


Use a fórmula na página OEIS para O(n^2 log n)complexidade, em vez de ingênuo O(n^6).

Explicação rápida:

  • Este código usa a fórmula a[n_] := 2*Sum[(n - k + 1)*(n - m + 1)*GCD[k - 1, m - 1], {m, 2, n}, {k, 2, n}] - n^2*((n^2 - 1)/6)descrita na seção de código do Mathematica.
  • Prova de fórmula:

    • A fórmula é equivalente a isso .

    • Seja o tamanho da caixa delimitadora de três pontos m * k. Considere 2 casos:

      • k != 0e m != 0: Existem 2 maneiras de escolher a orientação dos três pontos ( \ou /), gcd(k-1, m-1)-1maneiras de escolher o ponto entre os outros 2 pontos e (n - k) × (n - m)maneiras de escolher a posição da caixa delimitadora.
      • k == 0ou m == 0: existem 2 maneiras de escolher a orientação ( |ou -), nmaneiras de escolher a linha / coluna na qual os pontos se encontram e Binomial[n, 3] == (n*(n-1)*(n-2)) / 6maneiras de escolher os pontos nessa linha / coluna.

Algumas notas poliglotas:

  • Funky realmente não tem palavra-chave return. No entanto, como o ATaco explicou , [Funky] acha que returné uma variável. Portanto, ele está analisando a expressão, que convenientemente não faz nada, e analisa a próxima expressão. E isso é usado como uma saída.
  • O Javascript usa ^como xor bit a bit, diferente do Funky, que usa ^como exponenciação. Então, n*ntem que ser usado em vez de n^2garantir a compatibilidade com Javascript.
  • Em Funky, todo operador ( +, -, *, etc.) têm a mesma precedência e associativos à direita, então expressões precisam ser entre parênteses corretamente.
user202729
fonte
1
O +1 não esperava uma poliglota.
ATaco 21/10
Não existe pentagonia, mas a hexagonia se encaixa bem.
NieDzejkob 21/10
Este bytecount já foi usado ... link
NieDzejkob 5/17/17
Portanto, para corrigir o problema do número de bytes, você poderia colocar esta resposta em 330 bytes? Eu vou cuidar do resto.
N17Dzejkob
[Resposta acolchoada para 332 bytes por causa de questões conflitantes bytecount, ver esta mensagem de chat ]
user202729
8

11. Pari / GP, 64 bytes, A000065

{a(n) = if( n<0, 0, polcoeff ( 1 / eta(x + x*O(x^n) ), n) - 1)};

Experimente online!

Próxima sequência

MD XF
fonte
Essa entrada é válida?
Leaky Nun
Você precisou obter 64 bytes? : P
totallyhuman
@totallyhuman yes:;_; I solved A000064 and you changed it. Downvoted.
Stephen
@totallyhuman compromises lol. ver bate
HyperNeutrino
Dang
Mr. Xcoder
8

281. Java 5, 11628 bytes, A000947

// package oeis_challenge;

import java.util.*;
import java.lang.*;

class Main {

//  static void assert(boolean cond) {
//      if (!cond)
//          throw new Error("Assertion failed!");
//  }

    /* Use the formula a(n) = A000063(n + 2) - A000936(n).
    It's unfair that I use the formula of "number of free polyenoid with n
    nodes and symmetry point group C_{2v}" (formula listed in A000063)
    without understanding why it's true...
    */

    static int catalan(int x) {
        int ans = 1;
        for (int i = 1; i <= x; ++i)
            ans = ans * (2*x+1-i) / i;
        return ans / -~x;
    }

    static int A63(int n) {
        int ans = catalan(n/2 - 1);
        if (n%4 == 0) ans -= catalan(n/4 - 1);
        if (n%6 == 0) ans -= catalan(n/6 - 1);
        return ans;
    }

    static class Point implements Comparable<Point> {
        final int x, y;
        Point(int _x, int _y) {
            x = _x; y = _y;
        }

        /// @return true if this is a point, false otherwise (this is a vector)
        public boolean isPoint() {
            return (x + y) % 3 != 0;
        }

        /// Translate this point by a vector.
        public Point add(Point p) {
            assert(this.isPoint() && ! p.isPoint());
            return new Point(x + p.x, y + p.y);
        }

        /// Reflect this point along x-axis.
        public Point reflectX() {
            return new Point(x - y, -y);
        }

        /// Rotate this point 60 degrees counter-clockwise.
        public Point rot60() {
            return new Point(x - y, x);
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Point)) return false;
            Point p = (Point) o;
            return x == p.x && y == p.y;
        }

        @Override
        public int hashCode() {
            return 21521 * (3491 + x) + y;
        }

        public String toString() {
            // return String.format("(%d, %d)", x, y);
            return String.format("setxy %d %d", x * 50 - y * 25, y * 40);
        }

        public int compareTo(Point p) {
            int a = Integer.valueOf(x).compareTo(p.x);
            if (a != 0) return a;
            return Integer.valueOf(y).compareTo(p.y);
        }

        /// Helper class.
        static interface Predicate {
            abstract boolean test(Point p);
        }

        static abstract class UnaryFunction {
            abstract Point apply(Point p);
        }

    }

    static class Edge implements Comparable<Edge> {
        final Point a, b; // guarantee a < b
        Edge(Point x, Point y) {
            assert x != y;
            if (x.compareTo(y) > 0) { // y < x
                a = y; b = x;
            } else {
                a = x; b = y;
            }
        }

        public int compareTo(Edge e) {
            int x = a.compareTo(e.a);
            if (x != 0) return x;
            return b.compareTo(e.b);
        }
    }

    /// A graph consists of multiple {@code Point}s.
    static class Graph {
        private HashMap<Point, Point> points;

        public Graph() {
            points = new HashMap<Point, Point>();
        }

        public Graph(Graph g) {
            points = new HashMap<Point, Point>(g.points);
        }

        public void add(Point p, Point root) {
            assert(p.isPoint());
            assert(root.isPoint());
            assert(p == root || points.containsKey(root));
            points.put(p, root);
        }

        public Graph map(Point.UnaryFunction fn) {
            Graph result = new Graph();
            for (Map.Entry<Point, Point> pq : points.entrySet()) {
                Point p = pq.getKey(), q = pq.getValue();
                assert(p.isPoint()) : p;
                assert(q.isPoint()) : q;
                p = fn.apply(p); assert(p.isPoint()) : p;
                q = fn.apply(q); assert(q.isPoint()) : q;
                result.points.put(p, q);
            }
            return result;
        }

        public Graph reflectX() {
            return this.map(new Point.UnaryFunction() {
                public Point apply(Point p) {
                    return p.reflectX();
                }
            });
        }

        public Graph rot60() {
            return this.map(new Point.UnaryFunction() {
                public Point apply(Point p) {
                    return p.rot60();
                }
            });
        }

        @Override
        public boolean equals(Object o) {
            if (o == null) return false;
            if (o.getClass() != getClass()) return false;
            Graph g = (Graph) o;
            return points.equals(g.points);
        }

        @Override
        public int hashCode() {
            return points.hashCode();
        }

        Graph[] expand(Point.Predicate fn) {
            List<Graph> result = new ArrayList<Graph>();

            for (Point p : points.keySet()) {
                int[] deltaX = new int[] { -1, 0, 1, 1,  0, -1};
                int[] deltaY = new int[] {  0, 1, 1, 0, -1, -1};
                for (int i = 6; i --> 0;) {
                    Point p1 = new Point(p.x + deltaX[i], p.y + deltaY[i]);
                    if (points.containsKey(p1) || !fn.test(p1)
                        || !p1.isPoint()) continue;

                    Graph g = new Graph(this);
                    g.add(p1, p);
                    result.add(g);
                }
            }

            return result.toArray(new Graph[0]);
        }

        public static Graph[] expand(Graph[] graphs, Point.Predicate fn) {
            Set<Graph> result = new HashSet<Graph>();

            for (Graph g0 : graphs) {
                Graph[] g = g0.expand(fn);
                for (Graph g1 : g) {
                    if (result.contains(g1)) continue;
                    result.add(g1);
                }
            }

            return result.toArray(new Graph[0]);
        }

        private Edge[] edges() {
            List<Edge> result = new ArrayList<Edge>();
            for (Map.Entry<Point, Point> pq : points.entrySet()) {
                Point p = pq.getKey(), q = pq.getValue();
                if (p.equals(q)) continue;
                result.add(new Edge(p, q));
            }
            return result.toArray(new Edge[0]);
        }

        /**
         * Check if two graphs are isomorphic... under translation.
         * @return {@code true} if {@code this} is isomorphic
         * under translation, {@code false} otherwise.
         */
        public boolean isomorphic(Graph g) {
            if (points.size() != g.points.size()) return false;
            Edge[] a = this.edges();
            Edge[] b = g.edges();
            Arrays.sort(a);
            Arrays.sort(b);

            // for (Edge e : b)
                // System.err.println(e.a + " - " + e.b);
            // System.err.println("------- >><< ");

            assert (a.length > 0);
            assert (a.length == b.length);
            int a_bx = a[0].a.x - b[0].a.x, a_by = a[0].a.y - b[0].a.y;
            for (int i = 0; i < a.length; ++i) {
                if (a_bx != a[i].a.x - b[i].a.x || 
                    a_by != a[i].a.y - b[i].a.y) return false;
                if (a_bx != a[i].b.x - b[i].b.x || 
                    a_by != a[i].b.y - b[i].b.y) return false;
            }

            return true;
        }

        // C_{2v}.
        public boolean correctSymmetry() {

            Graph[] graphs = new Graph[6];
            graphs[0] = this.reflectX();
            for (int i = 1; i < 6; ++i) graphs[i] = graphs[i-1].rot60();
            assert(graphs[5].rot60().isomorphic(graphs[0]));
            int count = 0;
            for (Graph g : graphs) {
                if (this.isomorphic(g)) ++count;
                // if (count >= 2) {
                    // return false;
                // }
            }
            // if (count > 1) System.err.format("too much: %d%n", count);
            assert(count > 0);
            return count == 1; // which is, basically, true
        }

        public void reflectSelfType2() {
            Graph g = this.map(new Point.UnaryFunction() {
                public Point apply(Point p) {
                    return new Point(p.y - p.x, p.y);
                }
            });

            Point p = new Point(1, 1);
            assert (p.equals(points.get(p)));

            points.putAll(g.points);

            assert (p.equals(points.get(p)));
            Point q = new Point(0, 1);
            assert (q.equals(points.get(q)));
            points.put(p, q);
        }

        public void reflectSelfX() {
            Graph g = this.reflectX();
            points.putAll(g.points); // duplicates doesn't matter
        }

    }

    static int A936(int n) {
        // if (true) return (new int[]{0, 0, 0, 1, 1, 2, 4, 4, 12, 10, 29, 27, 88, 76, 247, 217, 722, 638, 2134, 1901, 6413})[n];

        // some unreachable codes here for testing.
        int ans = 0;

        if (n % 2 == 0) { // reflection type 2. (through line 2x == y)
            Graph[] graphs = new Graph[1];
            graphs[0] = new Graph();

            Point p = new Point(1, 1);
            graphs[0].add(p, p);

            for (int i = n / 2 - 1; i --> 0;)
                graphs = Graph.expand(graphs, new Point.Predicate() {
                    public boolean test(Point p) {
                        return 2*p.x > p.y;
                    }
                });

            int count = 0;
            for (Graph g : graphs) {
                g.reflectSelfType2();
                if (g.correctSymmetry()) {
                    ++count;

                    // for (Edge e : g.edges())
                        // System.err.println(e.a + " - " + e.b);
                    // System.err.println("------*");

                    }
                // else System.err.println("Failed");
            }

            assert (count%2 == 0);

            // System.err.println("A936(" + n + ") count = " + count + " -> " + (count/2));

            ans += count / 2;

        }

        // Reflection type 1. (reflectX)

        Graph[] graphs = new Graph[1];
        graphs[0] = new Graph();

        Point p = new Point(1, 0);
        graphs[0].add(p, p);

        if (n % 2 == 0) graphs[0].add(new Point(2, 0), p);

        for (int i = (n-1) / 2; i --> 0;)
            graphs = Graph.expand(graphs, new Point.Predicate() {
                public boolean test(Point p) {
                    return p.y > 0;
                }
            });

        int count = 0;
        for (Graph g : graphs) {
            g.reflectSelfX();
            if (g.correctSymmetry()) {
                ++count;
                // for (Edge e : g.edges())

                    // System.err.printf(

                // "pu %s pd %s\n"
                // // "%s - %s%n"

                // , e.a, e.b);
                // System.err.println("-------/");

            }
            // else System.err.println("Failed");
        }

        if(n % 2 == 0) {
            assert(count % 2 == 0);
            count /= 2;
        }
        ans += count;

        // System.err.println("A936(" + n + ") = " + ans);

        return ans;
    }

    public static void main(String[] args) {

        // Probably
        if (! "1.5.0_22".equals(System.getProperty("java.version"))) {
            System.err.println("Warning: Java version is not 1.5.0_22");
        }

        // A936(6);

        for (int i = 0; i < 20; ++i)
            System.out.println(i + " | " + (A63(i+9) - A936(i+7)));
        //A936(i+2);
    }
}

Experimente online!


Nota:

  1. Testado localmente com Java 5. (para que o aviso não seja impresso - consulte a guia de depuração do TIO)
  2. Não. Sempre. Usar. Java. 1. É mais detalhado que o Java em geral.
  3. Isso pode quebrar a corrente.
  4. O intervalo (7 dias e 48 minutos) não é mais do que o intervalo criado por esta resposta , que é de 7 dias e 1 hora e 25 minutos depois que o anterior .
  5. Novo recorde em grande bytecount! Como eu (por engano?) Uso espaços em vez de guias, o número de bytes é maior que o necessário. Na minha máquina são 9550 bytes. (no momento da redação desta revisão)
  6. Próxima sequência .
  7. O código, em sua forma atual, imprime apenas os 20 primeiros termos da sequência. No entanto, é fácil de mudar para que ele imprime primeiros 1000 itens (pela mudança do 20em for (int i = 0; i < 20; ++i)a 1000)

Yay! Isso pode calcular mais termos do que os listados na página OEIS! (pela primeira vez, para um desafio que preciso usar Java), a menos que o OEIS tenha mais termos em algum lugar ...


Explicação rápida

Explicação da descrição da sequência.

A sequência solicita o número de polenoides não planares livres com grupo de simetria C 2v , em que:

  • polienoide: (modelo matemático de hidrocarbonetos de polieno) árvores (ou em caso degenerado, vértice único) podem ser incorporadas na estrutura hexagonal.

Por exemplo, considere as árvores

      O                O           O      O       (3)
      |                 \         /        \
      |                  \       /          \
O --- O --- O             O --- O            O --- O
      |                                             \
      |                    (2)                       \
 (1)  O                                               O

O primeiro não pode ser incorporado na estrutura hexagonal, enquanto o segundo pode. Essa incorporação específica é considerada diferente da terceira árvore.

  • polenoide não planar: incorporação de árvores de modo que exista dois vértices sobrepostos.

(2)e a (3)árvore acima são planares. Este, no entanto, não é plano:

   O---O O
  /       \
 /         \
O           O
 \         /
  \       /
   O --- O

(existem 7 vértices e 6 arestas)

  • polienoide livre: as variantes de um polienoide, que podem ser obtidas por rotação e reflexão, são contadas como uma.

  • Grupo C 2v : Os polienoides são contados apenas se tiverem dois planos de reflexão perpendiculares e não mais.

Por exemplo, o único polenoide com 2 vértices

O --- O

possui 3 planos de reflexão: o horizontal -, o vertical |e o paralelo à tela do computador . Isso é demais.

Por outro lado, este

O --- O
       \
        \
         O

tem 2 planos de reflexão: /e .


Explicação do método

E agora, a abordagem sobre como realmente contar o número.

Primeiro, aceito a fórmula a(n) = A000063(n + 2) - A000936(n)(listada na página OEIS) como garantida. Não li a explicação no jornal.

[TODO conserte esta parte]

Obviamente, contar planar é mais fácil do que contar não planar. É o que o jornal também faz.

Os polienoides geometricamente planos (sem vértices sobrepostos) são enumerados por programação de computador. Assim, o número de polienoides geometricamente não planares se torna acessível.

Então ... o programa conta o número de polienoides planares e subtrai-o do total.

Como a árvore é plana de qualquer maneira, obviamente tem o plano de reflexão. Portanto, a condição se resume a "contar o número de árvores com um eixo de reflexão em sua representação 2D".

A maneira ingênua seria gerar todas as árvores com nnós e verificar a simetria correta. No entanto, como queremos encontrar apenas o número de árvores com um eixo de reflexão, podemos gerar toda a meia-árvore possível em uma metade, espelhá-las através do eixo e verificar a simetria correta. Além disso, como os polienoides gerados são árvores (planares), devem tocar o eixo de reflexão exatamente uma vez.

A função public static Graph[] expand(Graph[] graphs, Point.Predicate fn)pega uma matriz de gráficos, cada um tem nnós, e gera uma matriz de gráfico, cada um tem n+1nós, não iguais entre si (em conversão) - de modo que o nó adicionado deve satisfazer o predicado fn.

Considere dois eixos possíveis de reflexão: um que passa por um vértice e coincide com as arestas ( x = 0) e outro que é o bissetor perpendicular de uma aresta ( 2x = y). Podemos usar apenas um deles, porque os gráficos gerados são isomórficos.

Portanto, para o primeiro eixo x = 0, partimos do gráfico base composto por um único nó (1, 0)(caso nseja ímpar) ou dois nós com uma aresta entre (1, 0) - (2, 0)(caso nseja par) e depois expandimos os nós de modo que y > 0. Isso é feito na seção "Tipo de reflexão 1" do programa e, em seguida, para cada gráfico gerado, reflita (espelhe) o próprio eixo X x = 0( g.reflectSelfX()) e verifique se a simetria correta está correta.

No entanto, observe que se né divisível por 2, dessa forma contamos cada gráfico duas vezes, porque também geramos sua imagem no espelho pelo eixo 2x = y + 3.

(observe os 2 laranja)

Semelhante para o eixo 2x = y, se (e somente se) né ainda, começamos a partir do ponto (1, 1), gerar gráficos de tal forma que 2*x > y, e refletir cada um deles ao longo do 2x = yeixo ( g.reflectSelfType2()), conectar (1, 0)com (1, 1), e verificar se eles têm simetria correta. Lembre-se de dividir por 2 também.

user202729
fonte
Dado que estava dormindo quando este (e o outro) foram postados, darei a você o benefício da dúvida e ainda não aceito resposta.
caird coinheringaahing
2
@cairdcoinheringaahing Você estava online 3 minutos antes do prazo ... #
user202729
Ah, a próxima sequência pode ser codificada ... (embora seja infinita) se eu a ler corretamente. O cálculo em si é --- muito --- muito fácil, então não faça isso.
user202729
7

6. R , 71 bytes, A000072

function(n)length(unique((t<-outer(r<-(0:2^n)^2,r*4,"+"))[t<=2^n&t>0]))

Experimente online!

Próxima sequência

Freira Furada
fonte
1
Pelo amor de Deus, não verifiquei a próxima sequência antes de publicar esta resposta.
Leaky Nun
Uma próxima sequência fácil não é uma vantagem estratégica?
BlackCap
@BlackCap Eles não podem responder duas vezes seguidas ou menos de uma hora após a última resposta.
Erik the Outgolfer
@EriktheOutgolferthe answer before the last posted (the one who didn't break the chain) will win
BlackCap
@BlackCap neste ponto que não vai acontecer
Stephen
7

26. TI-BASIC, 274 bytes , A000183

.5(1+√(5→θ
"int(.5+θ^X/√(5→Y₁
"2+Y₁(X-1)+Y₁(X+1→Y₂
{0,0,0,1,2,20→L₁
Prompt A
Lbl A
If A≤dim(L₁
Then
Disp L₁(A
Else
1+dim(L₁
(~1)^Ans(4Ans+Y₂(Ans))+(Ans/(Ans-1))((Ans+1))-(2Ans/(Ans-2))((Ans-3)L₁(Ans-2)+(~1)^AnsY₂(Ans-2))+(Ans/(Ans-3))((Ans-5)L₁(Ans-3)+2(~1)^(Ans-1)Y₂(Ans-3))+(Ans/(Ans-4))(L₁(Ans-4)+(~1)^(Ans-1)Y₂(Ans-4→L₁(Ans
Goto A
End

Avalia a fórmula recursiva encontrada no link OEIS.

Próxima sequência

Scott Milner
fonte
Ah, eu sabia quando o site foi desativado que seria uma corrida louca quando ele voltou a funcionar. Mal me venceu.
Silvio Mayolo
Eu não sabia que o site foi para baixo ...
Scott Milner
7

49. SageMath , 74 bytes, A000003

lambda n: len(BinaryQF_reduced_representatives(-4*n, primitive_only=True))

Experimente online!

Próxima sequência

alefalpha
fonte
E passei uma hora tentando resolver essa sequência usando JavaScript ... bem, vou ter que passar para a próxima ...
ETHproductions
7

76. Pigmeu , 4147 bytes, A000036

globaln: 0                                                                                           

Pi:: 3.141592653589793                                                                               

floor:: (number) {                                                                                   
    floatPart: number % 1                                                                            
    number >= 0 =>                                                                                   
    number - floatPart                                                                               
    number - floatPart - 1                                                                           
}                                                                                                    

fsqrt:: (number) {                                                                                   
    floor| number ^ 0.5                                                                              
}                                                                                                    

summation:: (f i imax) {                                                                             
    i > imax => 0                                                                                    
    (f| i) + summation| f, i + 1, imax                                                               
}                                                                                                    

absoluteValue:: (number) {                                                                           
    number < 0 => -number                                                                            
    number                                                                                           
}                                                                                                    

A:: (number) {                                                                                       
    globaln~: number                                                                                 
    1 + 4 * (fsqrt| number)                                                                          
       + 4 * (fsqrt| number / 2) ^ 2                                                                 
       + 8 * summation| (j){ fsqrt| globaln - j * j }, (fsqrt| number / 2) + 1, (fsqrt| number)      
}                                                                                                    

V:: (number) {                                                                  
    Pi * number                                                                      
}                                                                                    

P:: (number) {                                             
    (A| number) - (V| number)                               
}                                                           

recordMax: 0                                           
findRecord:: (searchIndex record recordCount) {                                    
    x: absoluteValue| P| searchIndex                                               
    (x > record && recordCount = recordMax - 1) => searchIndex                     
    x > record => findRecord| searchIndex + 1, x, recordCount + 1                  
    findRecord| searchIndex + 1, record, recordCount                               
}                                                                                  

A000099:: (number) {                                                                 
    recordMax~: number                                                              
    findRecord| 1, 0, 0                                                              
}                                                                               

A000035:: (number) {                                                                       
    floor| (P| (A000099| number)) + 0.5                                         
}                                                                               

Próxima sequência

Você pode executar o código nesta página . Por exemplo, você pode obter o 10º número na sequência copiando o código acima e adicionando:

alert| A000035| 10
Peter Olson
fonte
4
... a próxima sequência é incontestável ...
HyperNeutrino
1
@HyperNeutrino Eu sei: o PI fez isso de propósito #
Peter Olson
Mal ...>. <Mas, de qualquer maneira, vou apenas codificar os 4 elementos na sequência. Bastante fácil xD OP aprova-lo, aparentemente ¯ \ _ (ツ) _ / ¯
HyperNeutrino