Codegolf — Первая Последовательность Без Квадратных Разностей

Рассмотрим последовательность \$(a_n)\$, определенную следующим образом.

• \$a_0=0\$
• Для всех \$n=1, 2, 3, \dots\$ определите \$a_n\$ как наименьшее положительное целое число такое, что \$a_n-a_i\$ не является квадратным числом, для любого \$0\leq я

Другими словами, это первая лексикографически последовательность, в которой никакие два термина не отличаются друг от друга на квадрат. Доказано, что эта последовательность бесконечна и A030193 в OEIS. Последовательность начинается

 Input -> Output
0     -> 0
10    -> 34
40    -> 215
 

Испытание

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

• Принимает неотрицательное целое число n and returns or prints the n-th term of this sequence. Either 1-indexed or 0-indexed is acceptable.

• Принимает положительное целое число n and returns or prints the first n terms of this sequence

• Не принимает никаких входных данных и возвращает или печатает все члены последовательности с помощью бесконечного цикла или бесконечного списка.

Допускается любая разумная форма ввода и вывода.

Пример (индекс 0)

Правила

• Стандартные лазейки запрещены.

• Код гольфа: побеждает самая короткая программа в байтах для каждого языка.

#код-гольф #математика #число #последовательность #теория чисел

Питон 3, 67 байт

Не принимает никаких входных данных и печатает все члены последовательности с помощью бесконечного цикла.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  λ              # Start a recursive environment,

# to output the infinite sequence implicitly as result afterwards,
0               # starting a(0)=0,

# and where every following a(n) is calculated as follows:

λ            #  Push a list of the previous results of a(0)..a(n-1)

U           #  Pop and store this list in variable `X`

∞.Δ        #  Find the first positive integer [1,2,3,...] which is truthy for:

X       #   Push list `X`

α      #   Get for each the absolute difference with the current integer

Ų    #   Check for each whether it's a square number

≠   #   Invert each boolean, so we check they're NOT a square number

P  #   And check if this is truthy for all of them
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Руби, 72 62 57 50 47 байт

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

Печатает все члены последовательности бесконечно.

7 байт сохранил Дингус и еще 3 — Сизиф.

Руби 2.7+, 45 байт

Питон 3, 101 93 байта

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

Вводит положительное целое число \$n\$ и возвращает первые \$n\$ члены \$A030193\$.

Питон 3, 102 92 88 84 байт

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

-4 байта благодаря movatica

Шелуха, 17 байт

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

Возвращает бесконечный список. Заголовок используется для извлечения из него 10 элементов, чтобы можно было отобразить результат.

Объяснение

Ретина 0.8.2, 46 байт

Попробуйте онлайн! Выводит члены от 0ᵗʰ до nᵗʰ. Объяснение: Программа сначала сопоставляет члены 0ᵗʰ и nᵗʰ, которые изначально отличаются на ноль, а затем увеличивает член nᵗʰ. При следующем проходе цикла он обнаруживает, что член nᵗʰ отличается от первой записи на единицу, и поэтому увеличивает его снова. Разница теперь равна двум, поэтому эта пара терминов больше не соответствует. Вместо этого последующие проходы начинают увеличивать предыдущие члены, пока, наконец, член 1ˢᵗ не будет увеличен до двух. На этом этапе термин 0ᵗʰ не может быть соединен ни с каким другим термином, поэтому теперь термин 1ˢᵗ соединен с термином nᵗʰ, поскольку они оба являются двумя. Таким образом, член nᵗʰ увеличивается дважды до четырех. Однако на этом этапе члены 0ᵗʰ и nᵗʰ могут снова сопоставляться, поэтому член nᵗʰ увеличивается до пяти. Теперь дальнейшие проходы могут начать увеличивать предыдущие термины, пока, наконец, термин 2ⁿᵈ не будет увеличен до пяти. На данный момент исчерпаны все совпадения терминов 0ᵗʰ и 1ˢᵗ, термин 2ⁿᵈ теперь соединен с термином nᵗʰ. Как и раньше, он увеличивается дважды, затем последующие проходы увеличивают предыдущие члены, пока, наконец, член 3ʳᵈ не увеличивается до семи. В конце концов все члены увеличиваются до тех пор, пока не исчезнут два члена, отличающиеся на квадрат. (Однако важно, чтобы при каждом проходе увеличивался только один терм, иначе некоторые термы могут увеличиваться преждевременно, поскольку представляют собой сумму квадратов терма, значение которого само по себе все еще является суммой квадратов терма.)

Создайте массив из n+1 терминов, каждый из которых начинается с нуля.

Повторите, пока два члена имеют квадратную разницу...

... обновить одну пару терминов...

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

... и добавьте еще один к этому термину.

Преобразуйте каждый член в десятичный вид.

За счет 2 байтов использование просмотра назад позволяет увеличивать все условия одновременно, что значительно повышает производительность:

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

JavaScript (ES7), 66 байт

Возвращает н-й член, 0-индексированный.

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

Желе, 14 байты

Монадическая ссылка, принимающая целое положительное число \$N\$, которое дает список первых \$N\$ термов.

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

Как?

Итерирует к жадному решению. Было бы легче следовать, так как map(_(0)) but we can start the Stream.iterate(0::Nil)(s=>Stream.from(s(0)).find(x=> !s.exists(Set(0 to x:_*)map(a=>x-a*a))).get::s) -цикл с \$N\$ вместо \$0\$, сохраняя эти два байта.

В качестве примера n+1 -loop consider \$N=3\$:

Хаскелл, 56 байт

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

n=>{ a=[];//array of terms in the sequence for(i=0;a.length<n;i++) //loop until array length is n a.every(x=>(i-x)**.5%1) //check if square root of delta with each previous number in sequence is not an integer &&a.push(i);//then add to array print(a)//output array (return works too) } is an infinite list of the results.

Это черпает вдохновение из Ответ AZTECCO.

Р, 85 76 67 63 байт

Изменить: -9 байт благодаря Джузеппе, а затем -4 байта благодаря Кириллу Л.

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

Выводит бесконечную последовательность.

К (нгн/к), 31 29 байт

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

Возвращает n-й элемент серии (с индексом 0). Если приемлемо вернуть первый _=>{a=[];for(i=0;;i++)a.every(x=>(i-x)**.5%1)&&a.push(i);return a} terms of the sequence, the leading @A{ZmaA fAõ² l}fXÄ}h0ô 0ô # Starting with [0] @ }h # Add elements to the array until the length is n: A{ }fXÄ # Find the next integer A that returns 0: Zm # For each element already in the array: aA # Get the absolute difference between it and A f # Remove any elements that are also in: Aõ² # All squares up to A^2 l # Count how many elements are left можно отбросить, чтобы сэкономить два байта.

• 0ô return only the last item of the generated sequence
  • n run a fold-do loop, for g итерации, засеянные h
    • n run a fold-converge loop, fixing @A{ZmaA fAõ² l}fXÄ}h0ô (сгенерированная на данный момент последовательность), засеянная g@n_:=g@m_/;AtomQ@√(m-n)=Print@n i=0 g@i++~Do~∞ . this will stop when the next value in the sequence has been identified
      • Nest[#~Join~{While[Or@@AtomQ/@√(++k-#)];k}&,{k=0},#]& take the square root of the differences between the current loop value and each value in the generated sequence so far
      • for(){($a+=,+$n*!($a|?{!([Math]::Sqrt($n-$_)%1)}).Count)-eq$n++} check if any difference is a square number (i.e. if it has a remainder of zero after being mod'd by 1)
      • {x,...} increment the current loop value if it is not the next term in the sequence
  • y+|/ append the next value in the sequence

PowerShell, 76 75 69 64 байт

Не принимает никаких входных данных, выводит бесконечную серию (до максимума для 64-битного целого числа со знаком)

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

Язык Wolfram (Математика), 55 байт

возвращает первые n членов

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

-11 байт благодаря @att

Язык Wolfram (Математика), 51 байт

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

Выводит список на неопределенный срок.

Япт, 27 23 22 байта

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

Возвращает первый {...}[x]/0 numbers in the sequence. If you заменять 0 with x вместо этого он возвращает x{...}/0 th number in the sequence (0-indexed).

Улучшения:

• Использовано «разница находится в списке квадратов» вместо «квадратный корень из разницы является целым числом», чтобы сэкономить 4 байта, вдохновлено ответом Джонатана Аллана Джелли.
• Использовал {*|...} to initialize the array as suggested by AZTECCO

Объяснение:

JavaScript, 66 байт

Добавляет члены последовательности в массив с бесконечным циклом.

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

JavaScript (V8), 77 76 байт

Печатает первый s=0;repeat{s=c(F,s);show(+F);while(any((0:F)^2%in%(F-s)))F=F+1} terms of the sequence.

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

Объяснение

Дж, 35 байт

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

Данный >>> L = 3 ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 1], [1, 2], [1, 3], [4, 1], [4, 2], [4, 3], [9, 1], [9, 2], [9, 3], [16, 1], [16, 2], [16, 3]] ŻJ²p⁸§ -> [2, 3, 4, 5, 6, 7, 10, 11, 12, 17, 18, 19] ŻJ²p⁸§Ṭ¬TŻ -> [0, 1, 8, 9, 13, 14, 15, 16] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 1, 8] >>> L = [0, 1, 8] ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 0], [1, 1], [1, 8], [4, 0], [4, 1], [4, 8], [9, 0], [9, 1], [9, 8], [16, 0], [16, 1], [16, 8]] ŻJ²p⁸§ -> [1, 2, 9, 4, 5, 12, 9, 10, 17, 16, 17, 24] ŻJ²p⁸§Ṭ¬TŻ -> [0, 3, 6, 7, 8, 11, 13, 14, 15, 18, 19, 20, 21, 22, 23] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 3, 6] >>> L = [0, 3, 6] ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 0], [1, 3], [1, 6], [4, 0], [4, 3], [4, 6], [9, 0], [9, 3], [9, 6], [16, 0], [16, 3], [16, 6]] ŻJ²p⁸§ -> [1, 4, 7, 4, 7, 10, 9, 12, 15, 16, 19, 22] ŻJ²p⁸§Ṭ¬TŻ -> [0, 2, 3, 5, 6, 8, 11, 13, 14, 17, 18, 20, 21] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 2, 3] >>> L = [0, 2, 3] ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 0], [1, 2], [1, 3], [4, 0], [4, 2], [4, 3], [9, 0], [9, 2], [9, 3], [16, 0], [16, 2], [16, 3]] ŻJ²p⁸§ -> [1, 3, 4, 4, 6, 7, 9, 11, 12, 16, 18, 19] ŻJ²p⁸§Ṭ¬TŻ -> [0, 2, 5, 8, 10, 13, 14, 15, 17] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 2, 5] >>> L = [0, 2, 5] ŻJ² -> [1, 4, 9, 16] ŻJ²p⁸ -> [[1, 0], [1, 2], [1, 5], [4, 0], [4, 2], [4, 5], [9, 0], [9, 2], [9, 5], [16, 0], [16, 2], [16, 5]] ŻJ²p⁸§ -> [1, 3, 6, 4, 6, 9, 9, 11, 14, 16, 18, 21] ŻJ²p⁸§Ṭ¬TŻ -> [0, 2, 5, 7, 8, 10, 12, 13, 15, 17, 19, 20] ŻJ²p⁸§Ṭ¬TŻḣ -> [0, 2, 5] >>> [0, 2, 5] >>> seen previously, so stop the Ƭ-loop and yield: [3, [0, 1, 8], [0, 3, 6], [0, 2, 3], [0, 2, 5]] Ṫ -> [0, 2, 5] , returns the first Ƭ условия.

Скала, 109 байт

Попробуйте это в Скэсти!

Бесконечный поток.

Первые n элементов по 100 байт.

Это тот же самый код, только без 0ð... part at the end. Given an n, it gives the first n elements of the sequence, but in reverse.

Еще одно 100-байтовое решение

Попробуйте это в Скэсти

Объяснение:

Желе, 15 14 байт

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

Печатает первые n членов.

Если мы разрешим вывод первых n+1 элементов (как это делают некоторые ответы), то это будет 13 байт (без последнего символа).

-1 байт благодаря Джонатану Аллану

Хаскелл, 95 89 байт

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

• сэкономил 6 благодаря @Wheat Wizard!

• использует этот совет Не тратьте зря защиту «иначе»

• возвращает n-й термин с нулевым индексом

• f(n) — повторяется (!) n раз, начиная с [0] и добавляет следующий член.

• затем берет элемент впереди, потому что список перевернут.

, 34 байта

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

Со шлейфом (и небольшим dfn) 41 байт

, 99 байт

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

Принимает n в качестве входных данных и возвращает n-е число в последовательности (с индексом 0).С (ГКК)

, 78 байт

более короткое решение, очень медленное для n > 8

Изменить: -2 байта благодаря потолочному коту.

, 36 байт

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

байты

Выводит бесконечную последовательность.

Попробуйте онлайн. ¡λVoΛoS≠⌊√M≠⁰N);0 ;0 start with [0] ¡ iterate on this array, appending results: λ ) lambda function (argument → ⁰) Vo N first natural number where M≠⁰ differences with elements so far Λo are all S≠⌊√ not square? and changing ¡λVoΛoS≠⌊√M≠⁰N);0 Должно было быть 11 байт, если удалить f=lambda n,a=[],x=0:n and f(*[n,n-1,a,a+[x]][all((x-k)**.5or k in a)::2],x+1)or a ( f=lambda n,l=[],a=0:n and(any((a-b)**.5%1==0for b in l)and f(n,l,a+1)or f(n-1,l+[a],a+1))or l к 0.step{|x|$*<<p(x)if$*.all?{(x-_1)**0.5%1>0}} inside a nested loop ( 0.step{|x|$*<<p(x)if$*.all?{|i|(x-i)**0.5%1>0}} ), но, к сожалению, встроенная рекурсивная среда все еще имеет некоторые проблемы здесь и там и, по-видимому, пытается получить рекурсивный список

в данном случае) не работает.
Вывод первого значения \$n\$ или \$n^{th}\$ будет на 1 байт длиннее, чем бесконечный список: попробуйте первый \$n\$ онлайн или.

попробуйте \$n^{th}\$ от 0 онлайн