Положительное целое число k
- это число Леша, если
k
может быть выражен какi*i + j*j + i*j
дляi
,j
целых чисел.
Например, первые положительные числа Леша: 1
( i=1
, j=0
); 3
( i=j=1
); 4
( i=2
, j=0
); 7
( i=2
, j=1
); 9
( i=-3
, j=3
); ... Обратите внимание , что i
, j
для данных k
не являются уникальными. Например, 9
также могут быть получены с i=3
, j=0
.
Другие эквивалентные характеристики этих чисел:
k
может быть выраженно какi*i + j*j + i*j
дляi
,j
неотрицательных целых чисел. (Для каждой пары целых чиселi
,j
есть пара неотрицательных целых чисел , которое дает то жеk
)Существует ряд
k
смежных шестиугольников, которые образуют тесселяцию на шестиугольной сетке (см. Иллюстрации дляk = 4
и дляk = 7
). (Благодаря этому свойству эти номера находят применение в сетях мобильной сотовой связи .)Смотрите больше характеристик на странице OEIS последовательности.
Соревнование
Если задано положительное целое число , выведите правдивый результат, если это число Лошиана , или ложный результат в противном случае.
Программа или функция должна обрабатывать (скажем, менее чем за минуту) входные данные вплоть до 1000
или до ограничений типа данных.
Код гольф. Кратчайшие победы.
Контрольные примеры
Следующие числа должны вывести достоверный результат:
1, 4, 7, 12, 13, 108, 109, 192, 516, 999
Следующие числа должны вывести ложный результат:
2, 5, 10, 42, 101, 102, 128, 150, 501, 1000
источник
i, j non-negative integers
или9 (i=-3, j=3)
- какой это?Ответы:
Желе ,
119 байтПопробуйте онлайн! или проверьте все контрольные примеры .
Задний план
В Элементарных результатах о бинарной квадратичной форме a² + ab + b² автор доказывает следующую теорему о числах Лёшиана.
Как отмечено на соответствующей странице OEIS , поскольку все целые числа являются конгруэнтными 0 , 1 или 2 по модулю 3 , число 3 является единственным простым числом , которое конгруэнтно 0 , и все числа формы (6k + 1) являются конгруэнтными 1 , теорема может быть сформулирована альтернативно следующим образом.
Неотрицательное целое число n является лёшевым числом тогда и только тогда, когда все простые множители n , конгруэнтные 2 по модулю 3, имеют четные показатели.
Как это работает
источник
Retina ,
6663454336 байтНесмотря на заголовок «Retina», это просто обычное регулярное выражение .NET, которое принимает унарные представления чисел Лоше.
Входы 999 и 1000 занимают меньше секунды.
Попробуйте онлайн! (Первая строка включает набор тестов, разделенных переводом строки, а следующие две для удобства занимаются преобразованием в унарный.)
объяснение
Решение основано на классификации, согласно которой входные данные могут быть записаны как
i*i + j*(i + j)
положительныеi
и неотрицательныеj
(поскольку нам не нужно обрабатывать ввод0
), и этоn*n
всего лишь сумма первыхn
нечетных целых чисел. Игра в гольф была интересным упражнением в прямом обращении.«Прямая ссылка» - это когда вы помещаете обратную ссылку в группу, к которой она относится. Конечно, это не работает, когда группа используется в первый раз, так как обратная ссылка еще не на что, но если вы поместите это в цикл, то обратная ссылка каждый раз получает перехват предыдущей итерации. Это, в свою очередь, позволит вам создавать больший захват с каждой итерацией. Это может быть использовано для создания очень компактных моделей для таких вещей, как треугольные числа, квадраты и числа Фибоначчи.
В качестве примера, используя тот факт, что квадраты являются просто суммами первых
n
нечетных целых чисел, мы можем сопоставить квадратные данные следующим образом:На первой итерации
..\1
не может работать, потому что\1
еще не имеет значения. Итак, мы начнем с^.
захвата одного персонажа в группу1
. На последующих итерациях^.
больше не совпадает из-за привязки, но теперь..\1
действует. Он соответствует на два символа больше, чем в предыдущей итерации, и обновляет захват. Таким образом, мы сопоставляем увеличивающиеся нечетные числа, получая квадрат после каждой итерации.К сожалению, сейчас мы не можем использовать эту технику как есть. После сопоставления
i*i
нам нужно получитьi
также, чтобы мы могли умножить его наj
. Простой (но долгий) способ сделать это состоит в том, чтобы использовать тот факт, что сопоставлениеi*i
требуетi
итераций, поэтому мы собираем данныеi
в группе1
. Теперь мы могли бы использовать балансировочные группы, чтобы извлечь этоi
, но, как я сказал, это дорого.Вместо этого я нашел другой способ записать эту «сумму последовательных нечетных целых чисел», которая также дает
i
в конце группу захвата. Конечно,i
нечетное число просто2i-1
. Это дает нам возможность увеличивать прямую ссылку только на 1 на каждой итерации. Вот эта часть:Это
()
просто помещает пустой захват в группу1
(инициализируяi
в0
). Это в значительной степени эквивалентно^.|
приведенному выше простому решению, но использование|
в этом случае будет немного сложнее.Тогда у нас есть основной цикл
(\1(?<1>.\1))
.\1
соответствует предыдущемуi
,(?<1>.\1)
затем обновляет группу1
с помощьюi+1
. Что касается новогоi
, мы только что подобрали2i-1
персонажей. Именно то, что нам нужно.Когда мы закончим, мы сопоставим некоторый квадрат,
i*i
и группа1
все еще содержитi
символы.Вторая часть ближе к простому квадратному соответствию, которое я показал выше. Давайте
1
пока проигнорируем обратную ссылку на :Это в основном то же самое
(^.|..\4)*
, за исключением того, что мы не можем использовать,^
потому что мы не в начале строки. Вместо этого мы используем условное, чтобы сопоставить дополнительное.\1
только тогда, когда мы уже использовали группу4
. Но на самом деле это точно так же. Это дает намj*j
.Единственное, чего не хватает, это
j*i
термин. Мы комбинируем это сj*j
использованием факта, чтоj*j
вычисления все еще требуютj
итераций. Таким образом , для каждой итерации мы также продвигать курсорi
с\1
. Нам просто нужно убедиться, что не записать это в группу4
, потому что это будет мешать совпадению последовательных нечетных чисел. Вот как мы приходим к:источник
CJam (
1615 байт)Онлайн демо
Это блок ( «анонимные функции») , который принимает данные в стеке и листьев
0
или1
в стеке. Он использует характеристику, что число является лешиановским, если оно не имеет простого множителя, равного 2 mod 3 с нечетной кратностью.Спасибо Деннису за однобайтовую экономию.
источник
Python 2, 56 байт
источник
Haskell, 42 байта
Пример использования:
f 501
->False
.Старается все комбинации
i
от0
доk
иj
от0
доi
.or
возвращает,True
если равенствоk==i*i+j*j+i*j
выполнено хотя бы для одной из комбинаций.@flawr нашел немного другую версию с тем же количеством байтов:
источник
or
, круто =) Может быть , у вас есть идея , как гольфы этой альтернативной формулировка:f k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]
?Java 8, 81 байт
простая, наивная реализация. по совпадению тот же код, что и в C #, но использует
->
вместо=>
.источник
;
. ЧЕРТ!i
илиj
.Python, 67 байт
https://repl.it/Cj6x
источник
Желе ,
15141312 байт1 байт благодаря милям.
Попробуйте онлайн!
Проверьте меньшие тестовые случаи .
Совет при тестировании большого количества (больше 50): не надо.
Истина - это положительное число. Фолси ноль.
объяснение
источник
Медуза ,
5643412928 байт2 байта благодаря Zgarb
Попробуйте онлайн!
Вилка моего желе отвечает .
источник
MATL ,
1413 байтПопробуйте онлайн! Или проверьте все тестовые случаи .
Выходы
1
или0
.объяснение
источник
Python, 49 байт
Использует эквивалентную квадратичную форму, заданную на OEIS of
n == 3*i*i+j*j
. Проверьте,n-3*i*i
является ли квадрат идеальным для любогоi
, взяв его квадратный корень и проверив, является ли оно целым числом, т. Е. Равно 0 по модулю 1. Обратите внимание, что Python точно вычисляет квадратные корни из идеальных квадратов без ошибки с плавающей запятой. Это+0j
делает его комплексным числом, чтобы избежать ошибки в квадратном корне из отрицания.источник
C (gcc),
7169 байтисточник
i,j,r;f(n){for(r=i=n+1;i--;)for(j=n;j--;)r*=n!=i*i+j*j+i*j;return!r;}
.i
илиj
.i
иj
.k
, но неi
аj
. Присмотритесь к примерам.k
может быть выражено какi*i + j*j + i*j
дляi, j
неотрицательных целых чисел». Вы присмотритесь.C #,
848281 байтНаивное решение. 1 = правда, 0 = ложь
источник
VBA,
6867 байтНаивный поиск, начинающий слегка замедляться при n = 1000. Excel распознает нулевой возврат как ложный, а все остальные возвращается как правдивый.
Обратите внимание, что исследование отрицательных значений i и j не требуется, поскольку дано i> j> = 0 :
(тот же результат, что и для i и j )
(если один отрицательный, не имеет значения, какой), а затем
И поскольку оба (ij) и j неотрицательны, любое поколение чисел Леша с отрицательным числом может быть достигнуто с использованием неотрицательных чисел.
Сохраненный байт,
Next:Next
->Next b,a
благодаря Тейлор Скотт.источник
i
илиj
.Next:Next
вNext b,a
:End Function
в конце вашего решенияJavascript (с использованием внешней библиотеки - Enumerable) (63 байта)
Ссылка на библиотеку: https://github.com/mvegh1/Enumerable Объяснение кода: создайте диапазон целых чисел от 0 до k (назовите его диапазоном «i») и проверьте, удовлетворяет ли какой-либо «i» определенному предикату. Этот предикат создает диапазон от 0 до k (назовите его диапазоном «j») и проверяет, удовлетворяет ли какой-либо «j» определенному предикату. Этот предикат является формулой Лоше
источник
Perl 6 ,
52 5150 байтОбъяснение:
Тест:
источник
i
илиj
.(0..$_ X 0..$_)
производит пустой список , если$_
меньше0
, поэтому нет необходимости проверять негативi
иj
потому , что они никогда не будут отрицательными. Так как предполагается, что он работает толькоTrue
для положительного числа Леша, мне не нужно делать ничего особенного для отрицательного случая.9 = (3*3)+(-3*-3)+(3*-3)
является положительным по Loeschiani=3, j=-3
; НО я перечитал, что у каждого числа Леша есть неотрицательныеi
иj
. Поэтому искать отрицательные числа не обязательно. Так что на самом деле мы могли бы удалить эти комментарии. Извините за ошибки; моя вина.{grep ->(\i,\j){$_==i*i+j*j+i*j},(-$_..$_ X -$_..$_)}(9)
результата((-3,0),(-3,3),(0,-3),(0,3),(3,-3),(3,0))
. Честно говоря, я, вероятно, просто адаптировал это из других ответов.PowerShell v2 +,
635655 байтПринимает ввод
$k
, повторяет цикл дважды (внешний цикл$i = 0 to $k
, внутренний цикл$j = 0 to $i
), каждая итерация генерирует результатi*i + j*j + i*j
(сокращенный доi*(i+j) + j*j
). Эти результаты инкапсулируются в паренах и передаются в виде массива-eq$k
. Это действует как фильтр для выбора только элементов, которые равны входным данным. Выводит ненулевое значение (число назад) для truey или ничего (пусто) для falsey. Процессы1000
примерно за 15 секунд на моей машине.Тестовые случаи
источник
Perl, 54 + 1 (
-n
флаг) = 55 байтНеобходимо
-n
и-M5.010
флаги для запуска:Выводит некоторые данные, если число является числом Леша, и ничего другого.
Эта реализация довольно скучна, поэтому вот еще одна, для 87 байтов, на основе регулярных выражений, просто для глаз:
Осторожнее с этим, так как при возврате будет много памяти, поэтому не пытайтесь проверять слишком большие числа! (особенно числа, которые не Loeschians)
источник
Дьялог АПЛ , 19 байт
Проверяет, если k ∊ ( i + j ) ² - ij , для любых 0 ≤ i , j ≤ k .
⊢
является k∊
членом∘.
всех комбинаций×
i времен j,-⍨
вычтенных из2*⍨
квадрата+
i плюс j⍨
для всех i и j в0,
нуле с добавлением⍳
целых чисел от 1 до k1000 занимает 3,3 секунды на моем M540 и даже меньше на TryAPL .
источник
Matlab,
5352 байтаПростой поиск по всем возможностям.
Выводит пустой массив как ложное значение, а непустой вектор - как истинное значение.
Рассматривая матрицу из всех нулей как ложную, а матрицу не из всех нулей как правдивую, мы можем избавиться от
find
функции, результатом которой является решение4746 байт :Один байт сохранен благодаря @flawr
источник
(a+b).^2-a.*b==n
корочеC 66 байтов
Позвоните
f()
по номеру для проверки. Функция возвращает количество найденных решений.Попробуйте это на Ideone .
источник
Mathematica, 44 байта
Безымянная функция, принимающая целое число в качестве входных данных и возвращающая
True
илиFalse
. Команда0~Range~#~Tuples~2
создает все упорядоченные пары целых чисел как между0
входом, так и между ним#
. Функция(+##)^2-##&
вычисляет квадрат суммы своих аргументов минус произведение своих аргументов; при вызове двух аргументов,i
иj
это точно так,i^2+j^2+ij
как хотелось бы. Таким образом, эта функция вызывается для всех кортежей, а затемMemberQ[...,#]
проверяет, является ли ввод одним из результирующих значений.источник
ASP, 39 + 4 = 43 байта
Вывод: задача выполнима тогда и только тогда, когда k является лёшевым.
Программирование набора ответов - это логический язык, похожий на пролог. Я использую здесь реализацию Potassco , clingo .
Ввод берется из параметров (
-ck=
длиной 4 байта). Пример звонка:Выходной образец:
Пробовал с 1000:
Выходной образец:
Вы можете попробовать это в своем браузере ; К сожалению, этот метод не обрабатывает флаги вызова, поэтому вам нужно добавить строку
#const k=999
, чтобы он работал.Ungolfed & объяснил код:
источник
PHP, 70 байт
принимает входные данные из аргумента командной строки; выходит с
1
по номеру Лёшского, с0
остальным.Беги с
-nr
.сломать
источник