Один OEIS за другим

94

На 13/03/2018 16:45 UTC победителем является ответ № 345 от Скрубла . Это означает, что конкурс официально завершен, но вы можете продолжать публиковать ответы, если они следуют правилам.

Кроме того, просто быстрый крик в тройку ответов с точки зрения количества ответов:

1. NieDzejkob - 41 ответ

2. KSmarts - 30 ответов

3. Гипер Нейтрино - 26 ответов

Это цепочка ответов, в которой используются последовательности из OEIS и длина предыдущего представления.

Этот цепочечный вопрос ответа будет работать следующим образом:

  • Я выложу первый ответ. Все остальные решения должны исходить из этого.
  • Следующий пользователь (назовем их userA) найдет последовательность OEIS, в которой его порядковый номер (см. Ниже) равен длине моего кода.
  • Используя последовательность, они должны затем кодировать на неиспользуемом языке программу, которая принимает целое число в качестве входных данных n и выводит n-е число в этой последовательности.
  • Затем они публикуют свое решение после моего, и новый пользователь (userB) должен повторить то же самое.

nЙ член последовательности является термином п раз после того , как первый, работающим с первым значением является первым значением дано на его странице OEIS. В этом вопросе мы будем использовать 0-индексацию для этих последовательностей. Например, с A000242 и n = 3, правильный результат будет 25 .

Тем не мение!

Это не код-гольф , поэтому самый короткий код не имеет значения. Но длина вашего кода все равно оказывает влияние. Чтобы предотвратить дублирование последовательностей, ваш счет должен быть уникальным . Это означает, что никакая другая представленная здесь программа не может иметь такую ​​же длину в байтах, как ваша.

Если для длины последнего сообщения нет последовательности, то последовательность для вашего сообщения является самой низкой неиспользуемой последовательностью. Это означает, что используемые последовательности также должны быть уникальными, и последовательность не может совпадать с вашей учетной записью.

После того, как ответ был опубликован и новые ответы не были опубликованы в течение более недели, победит ответ до того, как будет опубликован последний опубликованный ответ (тот, кто не разорвал цепочку).

Вход и выход

Применяются общие правила ввода и вывода. Входные данные должны быть целым числом или строковым представлением целого числа, а выходные данные должны быть правильными значениями в последовательности.

форматирование

Как и в большинстве вопросов, связанных с ответами , отформатируйте ответ следующим образом

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

`code`

[next sequence](link)

*anything else*

правила

  • Вы должны подождать не менее 1 часа, прежде чем отправлять ответ после публикации.
  • Вы не можете публиковать дважды (или более) подряд.
  • Номер индекса последовательности - это номер после Aдетали с удаленными начальными нулями (например, для A000040номера индекса 40).
  • Вы можете предположить, что ни ввод, ни требуемый вывод не будут выходить за пределы числового диапазона ваших языков, но, пожалуйста, не злоупотребляйте этим, выбирая язык, который может использовать только номер 1, например.
  • Если длина вашего сообщения превышает 65536 символов, укажите ссылку для доступа к коду (например, pastebin).
  • n никогда не будет больше 1000 или выходит за пределы последовательности, просто чтобы не допустить расхождения в точности, чтобы помешать языку конкурировать.
  • Каждые 150 (действительных) ответов увеличивают количество раз, когда язык может использоваться. Таким образом, после публикации 150 решений каждый язык может использоваться дважды (с учетом всех предыдущих ответов). Например, когда опубликовано 150 ответов, Python 3 может использоваться дважды, но из-за того, что он уже использовался один раз, это означает, что его можно использовать только один раз, пока не будет опубликовано 300 ответов.
  • Пожалуйста, помогите и опубликуйте ссылку на следующую последовательность, которая будет использоваться. Это не обязательно, но является рекомендацией.
  • Разные версии языков, например, Python 2 и Python 3, являются разными языками . Как правило, если обе версии доступны в Try It Online, это разные языки, но имейте в виду, что это общее правило, а не жесткий ответ.
  • Он не запрещен, но, пожалуйста, постарайтесь не копировать код со страницы OEIS, а попытаться его решить.
  • Жесткое кодирование допускается только в том случае, если последовательность конечна. Обратите внимание, что ответ, который вызвал это ( # 40 ), является исключением из правила. Несколько ответов на ранних этапах в жестком коде цепочки, но их можно игнорировать, поскольку нет смысла удалять цепочку, скажем, до # 100.

Фрагмент цепочки ответов

Показать фрагмент кода

math code-challenge sequence answer-chaining Caird Coneheringaahing
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Деннис
Это нормально, если программе потребуется лучшая точность с плавающей точкой для встроенного float/ doubleтипа, чтобы получить значения для большего n?
NieDzejkob
1
@Giuseppe Нет, поскольку вы генерируете числа, выполняя математику, а не просто помещая их в массив / строку
caird coinheringaahing
2
@cairdcoinheringaahing По моему мнению, это жесткое кодирование гамма-константы. Это не работает "в теории" для больших чисел.
user202729
6
Чат
user202729

Ответы:

4

345. брейнфук , 162 байта, A000301

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

Попробуйте онлайн!

Следующая последовательность!

Он принимает в качестве ввода символ с кодовой точкой n(согласно спецификациям BF) и выводит таким же образом. Чтобы увидеть цифры, я предлагаю использовать EsotericIDE @ Timwi .

Объяснение:

+<<,                                  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.

Так как при этом сохраняются все числа Фибоначчи, вплоть до важного, произойдет сбой для ДЕЙСТВИТЕЛЬНО большого ввода на ограниченной ленте.

Это может быть значительно сокращено путем жесткого кодирования базы (2), но игра в гольф не является проблемой вообще.

Хулдрасет на'Барья
источник
Когда следующий ответ (# 346) разорвал цепочку, ваш ответ - победитель!
Caird Coneheringaahing
1
@cairdcoinheringaahing Спасибо за этот удивительный вызов. Это огорчает меня, что это должно закончиться сейчас, но, как и все хорошие вещи в мире, конец это сделал. Теперь, чтобы сыграть в гольф это плохое оправдание для кода, потому что теперь это первый ответ, который кто-либо увидит, и он должен быть впечатляюще коротким ...
Khuldraeseth na'Barya
@ Scrooble, вы не можете изменить длину ...
NieDzejkob
@NieDzejkob Да, но я могу поиграть в гольф и добавить еще несколько прокладок, чтобы сохранить ту же длину.
Хулдрасет на'Барья
@cairdcoinheringaahing "разорвал цепь"? Что это обозначает?
Волшебная Урна Осьминога
40

22. FiM ++ , 982 байта, A000024

Примечание : если вы читаете это, вы можете отсортировать по «самым старым».

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

Следующая последовательность

судейская шапочка
источник
10
Хахаха, так сильно смеялся. +1 за выбор языка :-)
ETHproductions
Удивительно, возьми мое возражение
downrep_nation
22

1. Треугольный , 10 байтов, A000217

$\:_%i/2*<

Попробуйте онлайн!

Следующая последовательность

Как это устроено

Код форматируется в этот треугольник

   $
  \ :
 _ % i
/ 2 * <

с IP, начинающимся с $и перемещающимся на юго-восток (SE, хе), работает так:

$            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 Coneheringaahing
источник
13
1. Треугольный, 10 байтов, A000217. * следует по ссылке * A000217 Triangular numbers...
MD XF
22

73. Звездное , 363 байта, A000252

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

Попробуйте онлайн!

Следующая последовательность

Использует формулу « a(n) = n^4 * product p^(-3)(p^2 - 1)*(p - 1)где произведение находится над всеми простыми числами p, которые делят n» из OEIS.

Луна не работает, но эй, это не код-гольф.

Не дерево
источник
звезды на луне? Ммм
betseg
19

97. Python 3 (PyPy) , 1772 байта, A000236

Прежде всего, большое спасибо доктору Максу Алексееву за терпение ко мне. Мне очень повезло, что я смог связаться с ним по электронной почте, чтобы понять эту проблему. Его ответ по математике здесь очень помог мне. Спасибо Wheat Wizard за помощь. :)

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

Попробуйте онлайн!

Если это дает неправильный результат, просто увеличьте 100 до чего-то большего. Я думаю, 10000 будет работать на 4, но я оставлю свой компьютер включенным на ночь, чтобы подтвердить это; это может занять пару часов, чтобы закончить.

Обратите внимание, что часть (PyPy) предназначена для повторного использования Python. Я действительно не знаю многих других языков, и я не собираюсь пытаться перенести это на Java и рискую не закончить вовремя.

Следующая последовательность (Также, пожалуйста, не делайте больше сумасшедших математических заданий; у меня не осталось версий Python, так что кому-то еще придется сохранить этот вызов D :)

HyperNeutrino
источник
ну всегда есть pypy3
только для ASCII
15

107. TrumpScript , 1589 байт, 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.

Попробуйте онлайн!

При первом программировании на TrumpScript, возможно, я несколько раз изобрел колесо - 4 строки посвящены вычислению 2 ^ n. Я пытался сделать так, чтобы Трамп мог что-то сказать. В качестве бонуса, вот скрипт Python, который я написал, чтобы убедиться, что я все делаю правильно. Есть некоторые отличия от вышеупомянутой программы, но большая ее часть прямо эквивалентна.

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)

Следующая последовательность!

NieDzejkob
источник
3
I will make cat feel goodО_О
Бизнес Кот
К сожалению I will make Business Cat feel good, не будет работать ...
NieDzejkob
14

30. Python 1 , 1112 байт, 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

Попробуйте онлайн!

Даже не собираюсь беспокоиться об этом. Эй, это не самый длинный ответ Python на этом сайте!

Следующая последовательность

HyperNeutrino
источник
1
Поздравляем с расшифровкой математики: D
Утренняя монахиня
2
313 байт, смеется
Leaky Nun
@ LeakyNun Как я уже говорил, я не удосужился поиграть в гольф в этом лол. Кроме того, это не мой самый длинный ответ Python на этом сайте, поэтому idc: P, но приятно
HyperNeutrino
@LeakyNun И спасибо: D Мне потребовалось некоторое время, чтобы понять все это, LOL
HyperNeutrino
@LeakyNun 309 байт, потому что фактическое значение не _имеет значения; нам просто нужно повторить это много раз
HyperNeutrino
13

2. Haskell, 44 байта, A000010

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

Попробуйте онлайн!

Следующая последовательность

судейская шапочка
источник
12
Название следующей последовательности, хотя ...
полностью человек
@totallyhuman бедные кролики ...
Эрик Outgolfer
Должны ли мы ссылаться на предыдущий пост?
Утренняя монахиня
Мне больно, что я не могу играть в гольф сейчас. Я должен был быть первым, вы видите
BlackCap
Что это за следующая последовательность? Я не понимаю три: P
бета-распад
13

9. Pyth , 19 байтов, A000025

?>Q0sm@_B1-edld./Q1

Тестовый пакет .

Следующая последовательность

a (n) = количество разбиений n с четным рангом минус число с нечетным рангом. Ранг раздела является его наибольшей частью за вычетом количества частей.

Пропитанная монахиня
источник
Для тех, кто знает Pyth, я намеренно использовал >Q0вместо Qтого, чтобы, вы знаете, иметь следующую последовательность, которая будет A000019.
Утренняя монахиня
1
Со страницы OEISKeywords: easy,nice
BlackCap
@ LeakyNun Да, так как в противном случае мне пришлось бы решать A000017 ... брутто.
Эрик Outgolfer
12

8. Mathematica (10,1), 25 байтов, A000070

Tr@PartitionsP@Range@#+1&

Следующая последовательность

LegionMammal978
источник
Идеальная последовательность для использования Mathematica.
Утренняя монахиня
1
A000025 невероятно сложный. Вы должны добавить байт, чтобы получить A000026 вместо этого. : P
MD XF
12

206. Протон , 3275 байт, 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))

Попробуйте онлайн!

Следующая последовательность

HyperNeutrino
источник
Подождите, вы на самом деле это сделали? Если вы не пишете статью с этими ужасными программами и идете поговорить с каким-то профессором, вы
Стивен
@Stephen В настоящее время
исправление ошибок
Это подход расщепления треугольников, квадратов и пятиугольников в соответствии с Plantri? Похоже, что это может быть, но какой-то синтаксис незнаком.
Питер Тейлор
1
@PeterTaylor Предполагая, что я понимаю подход, который вы описываете, да, он ищет треугольники и помещает вершину, смежную со всеми 3 вершинами, или два смежных цикла и удаляет общее ребро и помещает вершину, смежную со всеми 4, то же самое для 3 треугольников. на пятиугольник. Я думаю, это то, что вы описываете.
HyperNeutrino
1
@ChristianSievers math.stackexchange.com/a/2463430/457091
HyperNeutrino
12

308. ENIAC (симулятор) , 3025 байт, A006060

псевдокод: 

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
}

Нет онлайн симулятора, результат выполнения: Устройство считывания карт Вывод перфокарты

Регистры и константы: 

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

Программный сигнал и поток данных: Программный поток сигналов и диаграмма потоков данных

Полный «код» на pastebin или в комментариях HTML в разметке этого ответа, чтобы предотвратить одновременный просмотр ссылки и довольно длинного ответа. Это весело!

Следующая последовательность

leo3065
источник
Не могли бы вы добавить ссылку на следующую последовательность, пожалуйста
Zacharý
@ Zacharý Ссылка находится в посте. Я перенесу его в конец поста, чтобы его было легче найти.
leo3065
12

15. CJam, 85 байт, A000060

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

Онлайн демо

Следующая последовательность

рассечение

OEIS дает

Gf: S (x) + S (x ^ 2) -S (x) ^ 2, где S (x) - производящая функция для A000151. - Паб Тер, 12 октября 2005 г.

где

S(Икс)знак равноИксΠя≥11(1-Икся)2s(я)знак равноИксΠя≥1(1+Икся+Икс2я+...)2s(я)
{           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)
Питер Тейлор
источник
1 минута и 33 секунды впереди меня ... пока я печатал объяснение
Leaky Nun
11

67. LOLCODE , 837 байтов, 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

Мой ключ от заглавной буквы обязательно должен сбежать, поэтому я написал все это, удерживая нажатой клавишу Shift.

Попробуйте онлайн!

Следующая последовательность

судейская шапочка
источник
+1 за использованиеPRAIME
Leaky Nun
3
Вы программист, вы могли бы написать это, а затем запустить его через скрипт Python, который upperэто
Стивен
5
@StepHen Или просто gggUGв VIM, где я написал это, но я не
настолько
10

10. Магма, 65 байт, A000019

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

Попробуй здесь

лол встроенный

Следующая последовательность

HyperNeutrino
источник
@ETHproductions :) нет проблем, спасибо странице OEIS, хотя она имеет точный встроенный там LOL
HyperNeutrino
4
; _; Я решил A000064, и вы изменили его. Downvoted.
Утренняя монахиня
Боже мой, так много последовательностей разделов
ETHproductions
Я случайно решил A007317 , пытаясь сделать это в Python ( TIO ): P
ETHproductions
Re-upvoted! \ o /
Дрянная монахиня
9

121. Пип , 525 байтов, 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

Онлайн демо

Следующая последовательность

Забавный факт: когда задача была впервые опубликована, я составил список небольших неприятных порядковых номеров, к которым я хотел стремиться с помощью CJam, и A000022 был в начале списка.

Это реализует функцию генерации, описанную в EM Rains и NJA Sloane, « О перечислении алканов (или 4-валентных деревьев» Кэли) , Journal of Integer Sequence, Vol. 2 (1999), взяв сумму за столько слагаемых, сколько необходимо для фиксирования коэффициента th, а затем выдвинув три четверти суммы. В частности, телескопирование первой половины означает, что индекс цикла должен применяться только к одному из них, а не ко всем из них.CknS4Th

Код разбивается как

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

Обратите внимание, что это моя первая в истории программа Pip, поэтому она, вероятно, не очень идиоматична.

Питер Тейлор
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Деннис
9

156. C # (моно), 2466 байт, A000083

Примечание: оценка составляет 2439 байт для кода и 27 для флага компилятора -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]);
        }
    }
}

Демо онлайн . Это полная программа, которая принимает данные из командной строки.

Следующая последовательность

рассечение

Я следую за комментарием Боуэна в OEIS о том, что генерирующая функция, в A000083(x) = A000237(x) + A035349(x) - A000237(x) * A035350(x)которой компонент, генерирующий функции, связан преобразованиями как

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

Я использую определения BIKи DIKиз https://oeis.org/transforms2.html, но формулы, похоже, содержат несколько опечаток. Я исправил это LPALбез особых затруднений и независимо вывел формулу, DIKоснованную на применении перечисления Полиа к индексу цикла диэдральной группы . Между № 121 и № 156 я много узнаю о перечислении Поли. Я представил некоторые ошибки , которые могут оказаться полезными для других людей, если эти преобразования снова появятся в цепочке.

Питер Тейлор
источник
8

13. VB.NET (.NET 4.5), 1246 байт, 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

Попробуйте онлайн!

Брайан Дж
источник
8

91. Python 2 (PyPy) , 1733 байта, 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

Попробуйте онлайн!

Я надеюсь, что использование Python 2 PyPy считается еще одной важной версией. Если бы кто-то мог достать мне интерпретатор Python 0, я бы тоже мог это использовать, но я надеюсь, что это действительно.

Это начинается в 1 вершине и работает, создавая представление матрицы смежности каждого возможного неориентированного графа с таким количеством вершин. Если он трехвалентный, он просматривает наборы ребер, которые будут отсортированы по длине. Если первый найденный цикл будет слишком коротким, он будет двигаться дальше. Если первый найденный цикл соответствует входу (смещение на 3), он выведет правильный счетчик вершин и завершит работу.

Следующая последовательность <- легко оторваться от всей этой математической чепухи: D

РЕДАКТИРОВАТЬ : я добавил некоторые оптимизации, чтобы сделать его немного быстрее (все еще не могу вычислить третий член в пределах 60-секундного лимита TIO), не меняя при этом байтовый счет.

HyperNeutrino
источник
... и я серьезно думал, что цепочка закончится ответом 90
pppery
1
@ppperry :) Мне нравится выполнять сложные задачи, потому что большинство людей даже не могут принять решение, поэтому мне не нужно беспокоиться о том, чтобы превзойти себя :) (например, проблема с
именем
Если кто-то не примет ваше решение и не переведет его на более краткий язык
pppery
@ppperry, что тоже o_O: P
HyperNeutrino
1
@HyperNeutrino Поздравляю с этим! Я волновался, что разорвал цепочку, и собирался заполнить счетчик байтов, чтобы указать на другую последовательность. Отличная работа!
Скотт Милнер
8

232. Funky , 326 330 332 байта, 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;
}

Попробуйте онлайн!

Полиглот с Javascript. Попробуйте онлайн!

Следующая последовательность .

Используйте формулу на странице OEIS для O(n^2 log n)сложности, а не наивный O(n^6).

Быстрое объяснение:

  • Этот код использует формулу, 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)описанную в разделе кода Mathematica.

  • Доказательство формулы:

    • Формула эквивалентна этому .

    • Пусть размер ограничивающей рамки из трех точек будет m * k. Рассмотрим 2 случая:

      • k != 0и m != 0: Есть 2 способа выбора ориентации трех точек ( \или /), gcd(k-1, m-1)-1способы выбора точки, лежащей между двумя другими точками, и (n - k) × (n - m)способы выбора положения ограничительной рамки.
      • k == 0или m == 0: Есть 2 способа выбора ориентации ( |или -), nспособы выбора строки / столбца, на котором лежат точки, и Binomial[n, 3] == (n*(n-1)*(n-2)) / 6способы выбора точек в этой строке / столбце.

Некоторые заметки полиглота:

  • У фанки на самом деле нет ключевого слова return. Однако, как объяснил ATaco , [Funky] считает returnпеременную. Таким образом, он анализирует это выражение, которое обычно ничего не делает, а затем анализирует следующее выражение. И это используется в качестве вывода.
  • Javascript используют ^как побитовый xor, в отличие от Funky, которые используют ^как возведение в степень. Поэтому n*nнеобходимо использовать вместо n^2обеспечения совместимости Javascript.
  • В фанках, весь оператор ( +, -, *и т.д.) имеет одинаковый приоритет и правоассоциативные, поэтому выражения должны быть в круглых скобках правильно.
user202729
источник
1
+1 не ожидал полиглота.
ATaco
Пентагонии нет, но гексагония хорошо вписывается.
NieDzejkob
Этот счет использовался уже ... ссылка
NieDzejkob
Итак, чтобы решить проблему с байтом, не могли бы вы дополнить этот ответ 330 байтами? Я позабочусь об остальном.
NieDzejkob
[Ответ дополняется до 332 байтов из-за конфликтующих проблем byountount, см. Это сообщение чата ]
user202729
8

11. Par / GP, 64 байта, A000065

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

Попробуйте онлайн!

Следующая последовательность

MD XF
источник
Это правильный вход?
Утренняя монахиня
Дидя должен получить 64 байта? : P
полностью человек
@totallyhuman да:;_; I solved A000064 and you changed it. Downvoted.
Стивен
@totallyhuman компромиссы лол. см. чат
HyperNeutrino
Dang
Mr. Xcoder
8

281. Java 5, 11628 байт, 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);
    }
}

Попробуйте онлайн!

Примечание:

  1. Протестировано локально с Java 5. (чтобы предупреждение не выводилось - см. Вкладку отладки TIO)
  2. Не. Когда-либо. Используйте. Ява. 1. Это более многословно, чем Java в целом.
  3. Это может разорвать цепь.
  4. Разрыв (7 дней и 48 минут) не больше, чем разрыв, созданный этим ответом , который на 7 дней и 1 час 25 минут позже предыдущего .
  5. Новый рекорд на большой счет! Поскольку я (ошибочно?) Использую пробелы вместо вкладок, количество байтов больше, чем необходимо. На моей машине это 9550 байт. (на момент написания этой редакции)
  6. Следующая последовательность .
  7. Код в его текущей форме печатает только первые 20 членов последовательности. Однако это легко изменить , чтобы он печатает первые 1000 пунктов ( в результате изменения в 20ин for (int i = 0; i < 20; ++i)к 1000)

Ура! Это может вычислить больше терминов, чем указано на странице OEIS! (впервые, для испытания мне нужно использовать Java), если у OEIS где-то больше терминов ...

Быстрое объяснение

Объяснение описания последовательности.

В последовательности задают номер свободного непланарного полиеноида с группой симметрии C 2v , где:

  • Полиеноид: (математическая модель полиеновых углеводородов) деревьев (или в вырожденном случае, одной вершины) с может быть встроен в гексагональную решетку.

Например, рассмотрим деревья

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

Первый не может быть встроен в гексагональную решетку, а второй может. Это конкретное вложение считается отличным от третьего дерева.

  • неплоский полиеноид: вложение деревьев так, что существует две перекрывающиеся вершины.

(2)а (3)дерево сверху плоское. Этот, однако, является неплоским:

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

(есть 7 вершин и 6 ребер)

  • свободный полиеноид: Варианты одного полиеноида, которые могут быть получены вращением и отражением, считаются единым целым.

  • Группа C 2v : Полиеноиды учитываются, только если они имеют 2 перпендикулярные плоскости отражения и не более.

Например, единственный полиеноид с 2 вершинами

O --- O

имеет 3 плоскости отражения: горизонтальную -, вертикальную |и параллельную экрану компьютера ■. Это слишком много.

С другой стороны, этот

O --- O
       \
        \
         O

имеет 2 плоскости отражения: /а ■.

Объяснение метода

А теперь подход о том, как на самом деле считать число.

Во-первых, я принимаю формулу a(n) = A000063(n + 2) - A000936(n)(приведенную на странице OEIS) как должное. Я не читал объяснение в газете.

[TODO исправить эту часть]

Конечно, считать планар проще, чем считать непланарно. Это то, что делает бумага тоже.

Геометрически плоские полиеноиды (без перекрывающихся вершин) подсчитываются с помощью компьютерного программирования. Таким образом, число геометрически неплоских полиеноидов становится доступным.

Итак ... программа подсчитывает количество плоских полиеноидов и вычитает их из общего числа.

Поскольку дерево в любом случае является плоским, оно, очевидно, имеет ■плоскость отражения. Таким образом, условие сводится к тому, чтобы «посчитать количество деревьев с осью отражения в его 2D представлении».

Наивным способом было бы сгенерировать все деревья с nузлами и проверить правильность симметрии. Однако, поскольку нам нужно только найти количество деревьев с осью отражения, мы можем просто сгенерировать все возможные полудерева на одной половине, отразить их через ось и затем проверить правильность симметрии. Более того, поскольку сгенерированные полиеноиды являются (плоскими) деревьями, он должен касаться оси отражения ровно один раз.

Функция public static Graph[] expand(Graph[] graphs, Point.Predicate fn)принимает массив графиков, каждый из которых имеет nузлы, и выводит массив графиков, каждый из которых имеет n+1узлы, не равные друг другу (при переводе), так что добавленный узел должен удовлетворять предикату fn.

Рассмотрим 2 возможных оси отражения: одна проходит через вершину и совпадает с ребрами ( x = 0), а другая - перпендикулярная биссектриса ребра ( 2x = y). Мы можем взять только один из них, потому что сгенерированные графы, в любом случае, изоморфны.

Итак, для первой оси x = 0мы начинаем с базового графа, состоящего из одного узла (1, 0)(в случае nнечетного) или двух узлов с ребром между (1, 0) - (2, 0)(в случае nчетного), а затем расширяем узлы так, чтобы y > 0. Это делается в разделе «Тип отражения 1» программы, а затем для каждого сгенерированного графа отражается (отражается) через ось X x = 0( g.reflectSelfX()), а затем проверяется, имеет ли он правильную симметрию.

Однако обратите внимание, что если nделится на 2, таким образом мы посчитали каждый граф дважды, потому что мы также генерируем его зеркальное отображение по оси 2x = y + 3.

(обратите внимание на 2 оранжевых)

Аналогично для оси 2x = y, если (и только если) nявляется четным, мы начинаем с точки (1, 1), генерируем графики таким образом, чтобы 2*x > yи отражали каждый из них по 2x = yоси ( g.reflectSelfType2()), соединялись (1, 0)с ними (1, 1)и проверяли, имеют ли они правильную симметрию. Не забудьте разделить на 2 тоже.

user202729
источник
Учитывая, что я спал, когда эта (и другая) была опубликована, я дам вам преимущество сомнения и пока не приму ответ.
Caird Coneheringaahing
2
@cairdcoinheringaahing Вы были в сети за 3 минуты до крайнего срока ...
user202729
О-о, следующая последовательность может быть жестко запрограммирована ... (хотя она бесконечна), если я правильно ее прочитал. Сам расчет - довольно - очень прост, поэтому не делайте этого.
user202729
7

6. R , 71 байт, A000072

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

Попробуйте онлайн!

Следующая последовательность

Пропитанная монахиня
источник
1
Ради любви к Богу, я не проверял следующую последовательность, прежде чем опубликовал этот ответ.
Утренняя монахиня
Разве легкая следующая последовательность не является стратегическим преимуществом?
BlackCap
@BlackCap Они не могут ответить дважды подряд или менее чем через 1 час после последнего ответа.
Эрик Outgolfer
@EriktheOutgolferthe answer before the last posted (the one who didn't break the chain) will win
BlackCap
@BlackCap на данный момент, что не произойдет
Стивен
7

26. TI-BASIC, 274 байта , 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

Оценивает рекурсивную формулу, найденную по ссылке OEIS.

Следующая последовательность

Скотт Милнер
источник
Ага, я знал, когда сайт вышел из строя, что это будет безумный рывок, когда он вернется. Еле избили меня.
Сильвио Майоло
Я не понимал, что сайт упал ...
Скотт Милнер
twitter.com/Nick_Craver/status/888553194313449472
Сильвио Майоло
7

76. Пигмей , 4147 байт, 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                                         
}

Следующая последовательность

Вы можете запустить код на этой странице . Например, вы можете получить 10-е число в последовательности, скопировав приведенный выше код и добавив:

alert| A000035| 10
Питер Олсон
источник
4
... следующая последовательность не вычислима ...
HyperNeutrino
1
@HyperNeutrino Я знаю: PI сделал это специально
Питер Олсон,
Зло ...>. <Но в любом случае, я просто жестко закодирую 4 элемента в последовательности. Достаточно просто xD OP одобряет это, по-видимому, ¯ \ _ (ツ) _ / ¯
HyperNeutrino