Satu demi satu OEIS

94

Pada 13/03/2018 16:45 UTC, pemenangnya adalah jawaban # 345 , oleh Scrooble . Ini berarti kontes telah berakhir secara resmi, tetapi jangan ragu untuk terus memposting jawaban, asalkan mereka mengikuti aturan.

Juga, cukup teriakan cepat ke tiga penjawab teratas dalam hal jumlah jawaban:

1. NieDzejkob - 41 jawaban

2. KSmarts - 30 jawaban

3. Hyper Neutrino - 26 jawaban


Ini adalah pertanyaan chaining jawaban yang menggunakan urutan dari OEIS, dan panjang pengiriman sebelumnya.

Pertanyaan chaining jawaban ini akan bekerja dengan cara berikut:

  • Saya akan memposting jawaban pertama. Semua solusi lain harus berasal dari itu.
  • Pengguna berikutnya (sebut saja mereka userA) akan menemukan urutan OEIS di mana nomor indeksnya (lihat di bawah) sama dengan panjang kode saya.
  • Dengan menggunakan urutan, mereka kemudian harus kode, dalam bahasa yang tidak digunakan , program yang mengambil integer sebagai input, n, dan menampilkan nomor ke-n dalam urutan itu.
  • Selanjutnya, mereka memposting solusi mereka setelah saya, dan pengguna baru (userB) harus mengulangi hal yang sama.

The njangka th berurutan adalah istilah n kali setelah yang pertama, bekerja dengan nilai pertama adalah nilai pertama diberikan pada halaman Oei nya. Dalam pertanyaan ini, kita akan menggunakan pengindeksan 0 untuk urutan ini. Misalnya, dengan A000242 dan n = 3, hasil yang benar adalah 25 .

Namun!

Ini bukan , jadi kode terpendek tidak masalah. Tetapi panjang kode Anda masih memiliki dampak. Untuk mencegah duplikasi urutan, bytecount Anda harus unik . Ini berarti bahwa tidak ada program lain yang dikirim di sini dapat memiliki panjang yang sama dengan byte Anda.

Jika tidak ada urutan untuk panjang posting terakhir, maka urutan untuk posting Anda adalah urutan terendah yang tidak digunakan. Ini berarti bahwa urutan yang digunakan juga harus unik, dan urutannya tidak boleh sama dengan bytecount Anda.

Setelah jawaban diposting dan tidak ada jawaban baru yang diposting lebih dari seminggu, jawaban sebelum posting terakhir (orang yang tidak memutuskan rantai) akan menang.

Masukan dan keluaran

Masukan umum dan aturan keluaran berlaku. Input harus berupa integer atau representasi string dari integer dan output harus nilai yang benar dalam urutan.

Memformat

Seperti sebagian besar jawaban, harap format jawaban Anda seperti ini

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

`code`

[next sequence](link)

*anything else*

Aturan

  • Anda harus menunggu setidaknya 1 jam sebelum memposting jawaban, setelah memposting.
  • Anda tidak boleh memposting dua kali (atau lebih) berturut-turut.
  • Nomor indeks urutan adalah nomor setelah Abagian, dan dengan nol di depan dihapus (misalnya untuk A000040nomor indeks adalah 40)
  • Anda dapat mengasumsikan bahwa input maupun output yang diperlukan tidak akan berada di luar rentang angka bahasa Anda, tapi tolong jangan menyalahgunakan ini dengan memilih bahasa yang hanya dapat menggunakan angka 1, misalnya.
  • Jika panjang kiriman Anda lebih besar dari 65536 karakter, harap berikan tautan ke cara untuk mengakses kode (misalnya pastebin).
  • n tidak akan pernah lebih besar dari 1000, atau berada di luar batas untuk urutan, hanya untuk mencegah perbedaan akurasi dari menghentikan bahasa dari persaingan.
  • Setiap 150 jawaban (valid), frekuensi penggunaan bahasa dapat meningkat. Jadi setelah 150 solusi telah diposting, setiap bahasa dapat digunakan dua kali (dengan semua jawaban sebelumnya dihitung untuk ini). Misalnya, ketika 150 jawaban telah diposting, Python 3 dapat digunakan dua kali, tetapi karena fakta bahwa itu telah digunakan sekali, ini berarti hanya dapat digunakan sekali lagi hingga 300 jawaban telah diposting.
  • Harap membantu dan memposting tautan ke urutan berikutnya untuk digunakan. Ini tidak wajib, tetapi merupakan rekomendasi.
  • Versi bahasa yang berbeda, misalnya Python 2 dan Python 3 adalah bahasa yang berbeda . Sebagai aturan umum, jika versi yang berbeda keduanya tersedia di Try It Online, mereka adalah bahasa yang berbeda, tetapi perlu diingat bahwa ini adalah aturan umum dan bukan jawaban yang kaku.
  • Itu tidak dilarang, tapi tolong jangan menyalin kode dari halaman OEIS, dan benar-benar mencoba menyelesaikannya.
  • Hardcoding hanya diperbolehkan jika urutannya terbatas. Harap perhatikan bahwa jawaban yang mendorong ini ( # 40 ) adalah pengecualian dari aturan. Beberapa jawaban di awal hardcode rantai, tetapi ini dapat diabaikan, karena tidak ada gunanya menghapus rantai hingga, katakanlah, # 100.

Cuplikan rantai jawaban

caird coinheringaahing
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Dennis
Apakah boleh jika suatu program membutuhkan akurasi floating-point yang lebih baik untuk builtin float/ doubletype untuk menghasilkan nilai yang lebih besar n?
NieDzejkob
1
@ Giuseppe Tidak, saat Anda menghasilkan angka dengan melakukan perhitungan, bukan hanya menempatkannya ke dalam array / string
caird coinheringaahing
2
@cairdcoinheringaahing Menurut saya itu adalah hardcoding konstanta gamma. Itu tidak bekerja "secara teori" untuk jumlah yang lebih besar.
user202729
6
Ruang obrolan
user202729

Jawaban:

4

345. brainfuck , 162 byte, A000301

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

Cobalah online!

Urutan selanjutnya!

Ini mengambil input karakter dengan titik kode n(menurut spesifikasi BF) dan output dengan cara yang sama. Untuk melihat angka-angka, saya sarankan menggunakan EsotericIDE @ Timwi .

Penjelasan:

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

Karena ini menyimpan semua angka Fibonacci hingga yang penting, itu akan gagal untuk input yang BENAR-BENAR besar pada pita terikat.

Ini bisa diperpendek secara signifikan dengan melakukan hardcoding pada base (2), tetapi golfiness tidak menjadi masalah sama sekali.

Khuldraeseth na'Barya
sumber
Saat jawaban berikutnya (# 346) memutus rantai, jawaban Anda adalah pemenangnya!
caird coinheringaahing
1
@cairdcoinheringaahing Terima kasih atas tantangan yang luar biasa ini. Menyedihkan saya bahwa ini harus berakhir sekarang, tetapi seperti melakukan semua hal baik di dunia, berakhirlah demikian. Sekarang untuk bermain golf, alasan buruk untuk kode ini, karena sekarang jawaban pertama yang akan dilihat siapa pun, dan itu pasti sangat singkat ...
Khuldraeseth na'Barya
@Scrooble Anda tidak dapat mengubah panjangnya ...
NieDzejkob
@NieDzejkob Ya, tapi saya bisa bermain golf dan menambahkan lebih banyak bantalan, untuk menjaga panjang yang sama.
Khuldraeseth na'Barya
@cairdcoinheringaahing "putus rantai"? Apa artinya?
Magic Gurita Guci
40

22. FiM ++ , 982 byte, A000024

Catatan : jika Anda membaca ini, Anda mungkin ingin mengurutkan berdasarkan "terlama".

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

Urutan berikutnya

BlackCap
sumber
10
Hahaha, tertawa terbahak-bahak melalui semua ini. +1 untuk pilihan bahasa :-)
ETHproduksi
Luar biasa, ambil upvote saya
downrep_nation
22

1. Triangular , 10 byte, A000217

$\:_%i/2*<

Cobalah online!

Urutan berikutnya

Bagaimana itu bekerja

Format kode ke dalam segitiga ini

   $
  \ :
 _ % i
/ 2 * <

dengan IP mulai dari $dan bergerak ke Tenggara (SE, heh), berfungsi seperti ini:

$            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
sumber
13
1. Triangular, 10 byte, A000217. * mengikuti tautan * A000217 Triangular numbers...
MD XF
22

73. Starry , 363 byte, A000252

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

Cobalah online!

Urutan berikutnya

Menggunakan rumus "di a(n) = n^4 * product p^(-3)(p^2 - 1)*(p - 1)mana produk berada di atas semua bilangan prima yang membagi n" dari OEIS.

Bulan adalah no-op, tapi hei, ini bukan kode-golf.

Bukan pohon
sumber
bintang di bulan? hmmm
betseg
19

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

Pertama-tama, banyak terima kasih kepada Dr. Max Alekseyev karena telah bersabar dengan saya. Saya sangat beruntung bisa menghubungi dia melalui email untuk memahami tantangan ini. Jawaban Math.SE-nya di sini banyak membantu saya. Terima kasih kepada Wheat Wizard karena telah membantu saya juga. :)

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

Cobalah online!

Jika itu memberikan hasil yang salah, cukup tambahkan 100 ke sesuatu yang lebih besar. Saya pikir 10000 akan bekerja untuk 4 tetapi saya akan membiarkan komputer saya berjalan semalam untuk mengkonfirmasi itu; mungkin butuh beberapa jam untuk menyelesaikannya.

Perhatikan bahwa bagian (PyPy) hanya supaya saya bisa menggunakan Python lagi. Saya benar-benar tidak tahu banyak bahasa lain dan saya tidak akan mencoba untuk port ini ke Jawa dan berisiko tidak selesai tepat waktu.

Next Sequence (Juga tolong jangan lakukan hal-hal gila lagi; Saya tidak punya versi Python yang tersisa sehingga orang lain harus menyelamatkan tantangan ini D :)

HyperNeutrino
sumber
baik selalu ada pypy3
ASCII-satunya
15

107. TrumpScript , 1589 byte, 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.

Cobalah online!

Pertama kali pemrograman dalam TrumpScript, ada kemungkinan bahwa saya menciptakan kembali roda beberapa kali - 4 baris didedikasikan untuk menghitung 2 ^ n. Saya mencoba membuatnya terlihat seperti sesuatu yang (mabuk) Trump bisa katakan. Sebagai bonus, ini adalah skrip Python yang saya tulis untuk memverifikasi bahwa saya melakukan semuanya dengan benar. Ada beberapa perbedaan dengan program di atas, tetapi banyak yang secara langsung setara.

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)

Urutan selanjutnya!

NieDzejkob
sumber
3
I will make cat feel goodO_O
Business Cat
Sayangnya I will make Business Cat feel goodtidak akan berhasil ...
NieDzejkob
14

30. Python 1 , 1112 byte, 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

Cobalah online!

Bahkan tidak akan repot dengan golf ini. Hei, itu bukan jawaban Python terlama saya di situs ini!

Urutan berikutnya

HyperNeutrino
sumber
1
Selamat atas decoding matematika: D
Leaky Nun
2
313 byte, lol
Leaky Nun
@ LeakyNun Seperti yang saya katakan, saya tidak repot-repot golf lol ini Selain itu, ini bukan jawaban Python terlama saya di situs ini jadi idc: P but nice
HyperNeutrino
@ LeakyNun Dan terima kasih: D Butuh waktu cukup lama untuk mengerti semuanya lol
HyperNeutrino
@ LeakyNun 309 byte karena nilai aktual _tidak relevan; kita hanya perlu mengulanginya berkali-kali
HyperNeutrino
13

2. Haskell, 44 byte, A000010

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

Cobalah online!

Urutan berikutnya

BlackCap
sumber
12
Namun, nama urutan berikutnya ...
manusiawi
@totallyhuman kelinci miskin ...
Erik the Outgolfer
Haruskah kita menautkan ke posting sebelumnya?
Leaky Nun
Sangat menyakitkan saya bahwa saya tidak bisa bermain golf sekarang. Saya harus menjadi yang pertama yang Anda lihat
BlackCap
Apa urutan selanjutnya? Saya tidak mengerti ketiga hal itu: P
Beta Decay
13

9. Pyth , 19 byte, A000025

?>Q0sm@_B1-edld./Q1

Suite uji .

Urutan berikutnya

a (n) = jumlah partisi n dengan pangkat genap angka minus dengan pangkat ganjil. Pangkat partisi adalah bagian terbesar dikurangi jumlah bagian.

Biarawati Bocor
sumber
Bagi mereka yang tahu Pyth, saya sengaja menggunakan >Q0bukannya Qagar, Anda tahu, memiliki urutan berikutnya menjadi A000019.
Leaky Nun
1
Dari halaman OEISKeywords: easy,nice
BlackCap
@ LeakyNun Ya karena kalau tidak saya harus memecahkan A000017 ... kotor.
Erik the Outgolfer
12

8. Mathematica (10.1), 25 byte, A000070

Tr@PartitionsP@Range@#+1&

Urutan berikutnya

LegionMammal978
sumber
Urutan sempurna untuk menggunakan Mathematica untuk.
Leaky Nun
1
A000025 adalah yang sangat sulit. Anda harus menambahkan byte untuk mendapatkan A000026. : P
MD XF
12

206. Proton , 3275 byte, 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))

Cobalah online!

Urutan berikutnya

HyperNeutrino
sumber
Tunggu, kamu benar-benar melakukannya? Jika Anda tidak menulis makalah dengan program-program aneh ini dan berbicara dengan beberapa profesor, Anda melewatkan sesuatu yang keren: P
Stephen
@Stephen Saat ini memperbaiki bug lol
HyperNeutrino
Apakah ini pendekatan pemisahan segitiga, bujur sangkar, dan segilima sesuai plantri? Sepertinya mungkin, tetapi beberapa sintaksinya tidak dikenal.
Peter Taylor
1
@PeterTaylor Dengan asumsi saya mengerti pendekatan yang Anda gambarkan, ya, ia mencari segitiga dan menempatkan simpul yang berdekatan dengan semua 3 simpul, atau dua siklus yang berdekatan dan menghapus tepi umum dan menempatkan simpul yang berdekatan dengan keempat, sama untuk 3 segitiga di atas pentagon. Saya pikir itu yang Anda gambarkan.
HyperNeutrino
1
@ChristianSievers math.stackexchange.com/a/2463430/457091
HyperNeutrino
12

308. ENIAC (simulator) , 3025 byte, A006060

Kodesemu:

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
}

Tidak ada simulator online, hasil eksekusi: Input pembaca kartu Keluaran kartu punch

Register dan konstanta:

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

Aliran sinyal program dan aliran data: Aliran sinyal program dan diagram alir data

"Kode" penuh pada pastebin atau dalam komentar HTML di markup jawaban ini, untuk mencegah linkrot dan jawaban yang cukup panjang untuk digulirkan secara bersamaan. Ini menyenangkan!

Urutan berikutnya

leo3065
sumber
Bisakah Anda menambahkan tautan ke urutan berikutnya, harap
Zacharý
@ Zacharý Tautan ada di pos. Saya akan memindahkannya ke akhir posting sehingga lebih mudah ditemukan.
leo3065
12

15. CJam, 85 byte, A000060

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

Demo online

Urutan berikutnya

Pembedahan

OEIS memberi

Gf: S (x) + S (x ^ 2) -S (x) ^ 2, di mana S (x) adalah fungsi pembangkit untuk A000151. - Pab Ter, 12 Okt 2005

dimana

S(x)=xsaya11(1-xsaya)2s(saya)=xsaya1(1+xsaya+x2saya+...)2s(saya)
{           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
sumber
1 menit dan 33 detik di depan saya ... ketika saya mengetikkan penjelasannya
Leaky Nun
11

67. LOLCODE , 837 byte, 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

Kunci capslock saya pasti akan lepas, jadi saya menulis semua ini sambil menahan shift ..

Cobalah online!

Urutan berikutnya

BlackCap
sumber
+1 untuk menggunakanPRAIME
Leaky Nun
3
Anda seorang programmer, Anda bisa menulis ini dan kemudian menjalankannya melalui skrip Python yang upperakan
Stephen
5
@ LANGKAH Atau hanya gggUGdalam vim di mana saya menulisnya, tapi saya tidak sepintar itu
BlackCap
10

10. Magma, 65 byte, A000019

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

Coba di sini

lol builtin

Urutan berikutnya

HyperNeutrino
sumber
@ ETHproductions :) tidak ada masalah, terima kasih halaman OEIS meskipun cuz memiliki persis builtin di sana lol
HyperNeutrino
4
; _; Saya memecahkan A000064 dan Anda mengubahnya. Diturunkan.
Leaky Nun
Ya ampun, begitu banyak sekuens partisi
ETHproduk
Saya tidak sengaja memecahkan A007317 ketika mencoba melakukan ini dengan Python ( TIO ): P
ETHproduk
Dipromosikan kembali! \ o /
Leaky Nun
9

121. Pip , 525 byte, 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

Demo online

Urutan berikutnya

Fakta menyenangkan: ketika tantangan pertama kali diposting, saya membuat daftar nomor urut jahat kecil yang ingin saya tuju dengan CJam, dan A000022 berada di bagian atas daftar.

Ini mengimplementasikan fungsi pembangkit yang dijelaskan dalam EM Rains dan NJA Sloane, On Cayley's Enumeration of Alkanes (atau 4-Valent Trees) , Journal of Integer Sequences, Vol. 2 (1999), mengambil jumlah untuk sebanyak istilah yang diperlukan untuk koefisien th untuk diperbaiki dan kemudian telescoping tiga perempat dari jumlah. Secara khusus, teleskop bagian pertama berarti bahwa indeks siklus hanya harus diterapkan ke salah satu daripada semua dari mereka.CknS4Th

Kode rusak menjadi

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

Perhatikan bahwa ini adalah program Pip pertama saya, jadi mungkin tidak terlalu idiomatis.

Peter Taylor
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Dennis
9

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

Catatan: skornya adalah 2439 byte untuk kode dan 27 untuk bendera kompiler -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]);
        }
    }
}

Demo online . Ini adalah program lengkap yang mengambil input dari baris perintah.

Urutan berikutnya

Pembedahan

Saya mengikuti komentar Bowen di OEIS bahwa fungsi pembangkit di A000083(x) = A000237(x) + A035349(x) - A000237(x) * A035350(x)mana fungsi pembangkit komponen terkait oleh transformasi sebagai

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

Saya menggunakan definisi dari BIKdan DIKdari https://oeis.org/transforms2.html tetapi rumus tampaknya memiliki sejumlah kesalahan ketik. Saya mengoreksi LPALtanpa banyak kesulitan, dan secara mandiri memperoleh formula untuk DIKdidasarkan pada penerapan enumerasi Pólya ke indeks siklus grup dihedral . Antara # 121 dan # 156 saya belajar banyak tentang pencacahan Pólya. Saya telah mengirimkan beberapa kesalahan , yang mungkin terbukti bermanfaat bagi orang lain jika transformasi ini muncul kembali dalam rantai.

Peter Taylor
sumber
8

13. VB.NET (.NET 4.5), 1246 byte, 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

Cobalah secara Online!

Brian J
sumber
8

91. Python 2 (PyPy) , 1733 byte, 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

Cobalah online!

Saya harap menggunakan Python 2 PyPy dianggap sebagai versi utama. Jika seseorang bisa memberi saya juru bahasa Python 0, saya bisa menggunakannya juga, tapi saya harap ini valid.

Ini dimulai pada 1 vertex dan bekerja, membuat representasi matriks adjacency dari setiap kemungkinan grafik tanpa arahan dengan banyak simpul. Jika trivalen, maka ia akan melihat melalui powerset dari tepi, yang akan diurutkan berdasarkan panjang. Jika siklus pertama yang ditemukan terlalu pendek, maka ia akan melanjutkan. Jika siklus pertama yang ditemukan cocok dengan input (diimbangi oleh 3) maka akan menghasilkan jumlah simpul yang benar dan berakhir.

Next Sequence <- semudah istirahat dari semua omong kosong matematika ini: D

EDIT : Saya menambahkan beberapa optimasi untuk membuatnya sedikit lebih cepat (masih tidak bisa menghitung istilah ketiga dalam batas 60 detik TIO) tanpa mengubah bytecount.

HyperNeutrino
sumber
... dan saya serius berpikir rantai itu akan berakhir dengan jawaban 90
pppery
1
@ppperry :) Saya suka melakukan tantangan berat karena kebanyakan orang bahkan tidak bisa membuat solusi jadi saya tidak perlu khawatir akan kalah :) (mis. masalah penamaan rantai karbon)
HyperNeutrino
Kecuali seseorang mengambil solusi Anda dan mengubahnya menjadi bahasa
terser
@pperry itu juga o_O: P
HyperNeutrino
1
@HyperNeutrino Selamat atas pemecahannya! Saya khawatir saya telah memutus rantai, dan sedang mempertimbangkan menambah jumlah byte untuk menunjuk ke urutan yang berbeda. Kerja bagus!
Scott Milner
8

232. Funky , 326 330 332 byte, 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;
}

Cobalah online!

Polyglot dengan Javascript. Cobalah online!

Urutan berikutnya .


Gunakan rumus pada halaman OEIS untuk O(n^2 log n)kompleksitas, alih-alih naif O(n^6).

Penjelasan cepat:

  • Kode ini menggunakan rumus yang 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)dijelaskan di bagian kode Mathematica.
  • Pembuktian formula:

    • Rumusnya setara dengan ini .

    • Biarkan ukuran kotak pembatas tiga poin menjadi m * k. Pertimbangkan 2 kasus:

      • k != 0dan m != 0: Ada 2 cara untuk memilih orientasi dari tiga titik ( \atau /), gcd(k-1, m-1)-1cara untuk memilih titik terletak di antara 2 titik lainnya, dan (n - k) × (n - m)cara untuk memilih posisi kotak pembatas.
      • k == 0atau m == 0: Ada 2 cara untuk memilih orientasi ( |atau -), ncara untuk memilih baris / kolom di mana titik terletak, dan Binomial[n, 3] == (n*(n-1)*(n-2)) / 6cara untuk memilih titik di baris / kolom itu.

Beberapa catatan polyglot:

  • Funky tidak benar-benar memiliki kata kunci return. Namun, seperti yang dijelaskan ATaco , [Funky] menganggap returnitu variabel. Jadi mem-parsing ekspresi itu, yang tidak melakukan apa-apa, lalu mem-parsing ekspresi selanjutnya. Dan ini digunakan sebagai output.
  • Javascript digunakan ^sebagai bitwise xor, tidak seperti Funky yang digunakan ^sebagai eksponensial. Jadi n*nharus digunakan daripada n^2memastikan kompatibilitas Javascript.
  • Dalam funky, semua operator ( +, -, *, dll) memiliki awalan yang sama dan kanan asosiatif, sehingga ekspresi perlu kurung benar.
pengguna202729
sumber
1
+1 tidak mengharapkan poliglot.
ATaco
Tidak ada Pentagony, tetapi Hexagony cocok.
NieDzejkob
Bytecount ini sudah digunakan ... tautan
NieDzejkob
Jadi, untuk memperbaiki masalah bytecount, bisa tolong pad jawaban ini hingga 330 byte? Saya akan menangani sisanya.
NieDzejkob
[Jawaban diisi hingga 332 byte karena masalah bytecount yang bertentangan, lihat pesan obrolan ini ]
user202729
8

11. Pari / GP, 64 byte, A000065

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

Cobalah online!

Urutan berikutnya

MD XF
sumber
Apakah itu input yang valid?
Leaky Nun
Didya harus mendapatkan 64 byte? : P
totallyhuman
@ benar-benar manusia ya:;_; I solved A000064 and you changed it. Downvoted.
Stephen
@totallyhuman kompromi lol. lihat obrolan
HyperNeutrino
Dang
Tn. Xcoder
8

281. Java 5, 11628 byte, 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);
    }
}

Cobalah online!


Catatan:

  1. Diuji secara lokal dengan Java 5. (sedemikian sehingga peringatan tidak dicetak - lihat tab debug TIO)
  2. Jangan. Pernah. Menggunakan. Jawa. 1. Ini lebih bertele-tele daripada Jawa secara umum.
  3. Ini dapat memutus rantai.
  4. Kesenjangan (7 hari dan 48 menit) tidak lebih dari jarak yang dibuat oleh jawaban ini , yaitu 7 hari dan 1 jam 25 menit kemudian dari yang sebelumnya .
  5. Rekor baru pada bytecount besar! Karena saya (secara keliru?) Menggunakan spasi alih-alih tab, bytecount lebih besar dari yang diperlukan. Di komputer saya ini adalah 9.550 byte. (pada saat penulisan revisi ini)
  6. Urutan berikutnya .
  7. Kode, dalam bentuk saat ini, hanya mencetak 20 syarat pertama dari urutan. Namun itu mudah untuk mengubah sehingga akan mencetak pertama 1000 item (oleh perubahan 20dalam for (int i = 0; i < 20; ++i)untuk 1000)

Yay! Ini dapat menghitung lebih banyak istilah daripada yang tercantum pada halaman OEIS! (untuk pertama kalinya, untuk tantangan saya perlu menggunakan Java) kecuali OEIS memiliki lebih banyak istilah di suatu tempat ...


Penjelasan cepat

Penjelasan deskripsi urutan.

Urutan meminta jumlah polyenoid nonplanar gratis dengan kelompok simetri C 2v , di mana:

  • polyenoid: (model matematika polyene hydrocarbon) pohon (atau dalam kasus degenerate, satu vertex) dengan dapat tertanam dalam kisi heksagonal.

Sebagai contoh, perhatikan pohon-pohonnya

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

Yang pertama tidak bisa tertanam dalam kisi heksagonal, sedangkan yang kedua bisa. Penanaman khusus itu dianggap berbeda dari pohon ketiga.

  • nonplanar polyenoid: penanaman pohon sedemikian rupa sehingga ada dua simpul yang tumpang tindih.

(2)dan (3)pohon di atas adalah planar. Yang ini, bagaimanapun, adalah nonplanar:

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

(ada 7 simpul dan 6 tepi)

  • polyenoid bebas: Varian dari satu polyenoid, yang dapat diperoleh dengan rotasi dan refleksi, dihitung sebagai satu.

  • Kelompok C 2v : Polyenoid hanya dihitung jika mereka memiliki 2 bidang pantulan tegak lurus, dan tidak lebih.

Misalnya, satu-satunya polyenoid dengan 2 simpul

O --- O

memiliki 3 bidang refleksi: Yang horizontal -, yang vertikal |, dan yang sejajar dengan layar komputer . Itu terlalu banyak.

Di sisi lain, yang ini

O --- O
       \
        \
         O

memiliki 2 bidang refleksi: /dan .


Penjelasan metode

Dan sekarang, pendekatan tentang bagaimana sebenarnya menghitung angka.

Pertama, saya menerima formula a(n) = A000063(n + 2) - A000936(n)(terdaftar pada halaman OEIS) begitu saja. Saya tidak membaca penjelasan di koran.

[TODO memperbaiki bagian ini]

Tentu saja, menghitung planar lebih mudah daripada menghitung nonplanar. Itu yang dilakukan koran juga.

Polenoid planar secara geometris (tanpa simpul yang tumpang tindih) dihitung dengan pemrograman komputer. Dengan demikian jumlah polenoid nonplanar yang geometris dapat diakses.

Jadi ... program menghitung jumlah polenoid planar, dan kurangi dari total.

Karena pohon itu planar, jelas memiliki bidang pantulan. Jadi kondisinya bermuara pada "hitung jumlah pohon dengan sumbu refleksi dalam representasi 2D-nya".

Cara naif akan menghasilkan semua pohon dengan nnode, dan periksa simetri yang benar. Namun, karena kami hanya ingin menemukan jumlah pohon dengan sumbu refleksi, kami hanya dapat menghasilkan semua setengah pohon yang mungkin pada satu setengah, mirror mereka melalui sumbu, dan kemudian periksa simetri yang benar. Selain itu, karena polenoid yang dihasilkan adalah pohon (planar), ia harus menyentuh sumbu refleksi tepat sekali.

Fungsi ini public static Graph[] expand(Graph[] graphs, Point.Predicate fn)mengambil array grafik, masing-masing memiliki nnode, dan output array grafik, masing-masing memiliki n+1node, tidak sama satu sama lain (dalam terjemahan) - sehingga simpul yang ditambahkan harus memenuhi predikat fn.

Pertimbangkan 2 sumbu refleksi yang mungkin: Yang melewati titik dan bertepatan dengan tepi ( x = 0), dan yang merupakan garis-bagi tegak lurus dari tepi ( 2x = y). Kita hanya dapat mengambil salah satunya saja karena grafik yang dihasilkan adalah isomorfik.

Jadi, untuk sumbu pertama x = 0, kita mulai dari grafik dasar yang terdiri dari satu simpul (1, 0)(dalam kasus nganjil) atau dua node dengan tepi antara (1, 0) - (2, 0)(dalam kasus ngenap), dan kemudian perluas simpul sedemikian rupa y > 0. Itu dilakukan oleh bagian "Refleksi tipe 1" dari program, dan kemudian untuk setiap grafik yang dihasilkan, refleksikan (mirror) itu sendiri melalui sumbu X x = 0( g.reflectSelfX()), dan kemudian periksa apakah ia memiliki simetri yang benar.

Namun, perhatikan bahwa jika nhabis dibagi 2, dengan cara ini kami menghitung setiap grafik dua kali, karena kami juga menghasilkan gambar cermin oleh sumbu 2x = y + 3.

(perhatikan 2 yang oranye)

Mirip dengan sumbu 2x = y, jika (dan hanya jika) nadalah genap, kita mulai dari titik (1, 1), menghasilkan grafik sedemikian rupa 2*x > y, dan merefleksikan masing-masing dari mereka di atas 2x = ysumbu ( g.reflectSelfType2()), terhubung (1, 0)dengan (1, 1), dan periksa apakah mereka memiliki simetri yang benar. Ingatlah untuk membagi dengan 2 juga.

pengguna202729
sumber
Mengingat saya tertidur ketika ini (dan yang lainnya) diposting, saya akan memberi Anda manfaat dari keraguan dan belum menerima jawaban.
caird coinheringaahing
2
@cairdcoinheringaahing Anda online 3 menit sebelum batas waktu ...
user202729
Uh oh, urutan selanjutnya bisa hard-coded ... (meskipun tidak terbatas) jika saya membacanya dengan benar. Perhitungannya sendiri --- cukup --- sangat mudah, jadi jangan lakukan itu.
user202729
7

6. R , 71 byte, A000072

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

Cobalah online!

Urutan berikutnya

Biarawati Bocor
sumber
1
Demi kasih Tuhan, saya tidak memeriksa urutan selanjutnya sebelum saya memposting jawaban ini.
Leaky Nun
Bukankah urutan berikutnya yang mudah merupakan keuntungan strategis?
BlackCap
@ Blacklap Mereka tidak dapat menjawab dua kali berturut-turut atau kurang dari 1 jam setelah mereka menjawab terakhir.
Erik the Outgolfer
@EriktheOutgolferthe answer before the last posted (the one who didn't break the chain) will win
BlackCap
@ BlackCap pada titik ini yang tidak akan terjadi
Stephen
7

26. TI-BASIC, 274 byte , 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

Mengevaluasi rumus rekursif yang ditemukan di tautan OEIS.

Urutan berikutnya

Scott Milner
sumber
Agh saya tahu ketika situs turun bahwa itu akan menjadi terburu-buru ketika kembali. Baru saja mengalahkan saya.
Silvio Mayolo
Saya tidak menyadari situsnya turun ...
Scott Milner
7

49. SageMath , 74 byte, A000003

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

Cobalah online!

Urutan berikutnya

alephalpha
sumber
Dan saya hanya menghabiskan waktu satu jam untuk mencoba urutan ini menggunakan JavaScript ... oh well, saya harus pindah ke yang berikutnya ...
ETHproduksi
7

76. Pygmy , 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                                         
}                                                                               

Urutan berikutnya

Anda dapat menjalankan kode di halaman ini . Misalnya, Anda bisa mendapatkan nomor 10 dalam urutan dengan menyalin kode di atas dan menambahkan:

alert| A000035| 10
Peter Olson
sumber
4
... urutan selanjutnya tidak dapat dihitung ...
HyperNeutrino
1
@HyperNeutrino Saya tahu: PI melakukan ini dengan sengaja
Peter Olson
Jahat ...>. <Tapi bagaimanapun, saya hanya akan meng-hardcode 4 elemen dalam urutan. Cukup mudah xD OP menyetujui itu rupanya ¯ \ _ (ツ) _ / ¯
HyperNeutrino