Связанная последовательность OEIS: A008867
Усеченное треугольное число
Общим свойством треугольных чисел является то, что они могут быть расположены в виде треугольника. Например, возьмите 21 и расположите в треугольник o
s:
о оо ооо оооо ооооо оооооо
Давайте определим «усечение»: разрезание треугольников одинакового размера с каждого угла. Один из способов усечь 21 заключается в следующем:
, , , ооо оооо , ооо , , ооо ,
(Треугольники .
вырезаны из оригинала).
Осталось 12 o
с, поэтому 12 - это усеченное число треугольника.
задача
Ваша задача - написать программу или функцию (или эквивалент), которая принимает целое число и возвращает (или использует любой из стандартных методов вывода), является ли число усеченным числом треугольника.
правила
- Нет стандартных лазеек.
- Входные данные - неотрицательное целое число.
- Вырез не может иметь длину стороны, превышающую половину длины исходного треугольника (т.е. разрезы не могут перекрываться)
- Срез может иметь длину стороны ноль.
Контрольные примеры
Truthy:
0
1
3
6
7
10
12
15
18
19
Falsy:
2
4
5
8
9
11
13
14
16
17
20
Тестовые случаи для всех целых чисел до 50: TIO Link
Это код-гольф , поэтому выигрыши с кратчайшим количеством байтов на каждом языке!
источник
Ответы:
Haskell,
4645 байтПопробуйте онлайн!
источник
Haskell , 46 байтов
Попробуйте онлайн!
Бросив кучу теории чисел в проблему (спасибо @flawr), я нашел эту характеристику:
Это означает, например, что 4n-1 может не делиться на 5, если он не делится на 5 2 = 25, а общее число 5 факторов является четным.
В Haskell нет встроенной факторизации, но мы можем импровизировать. Если мы работаем с факторизациями в простые числа типа 12 = 3 * 4 , мы можем использовать эквивалентное утверждение:
Мы можем извлечь степень простого числа p, появляющегося в k как
gcd(p^k)k
. Затем мы проверяем, что результат r не 5 или 7 по модулю 12, какmod(r-5)12>2
. Обратите внимание, что r нечетно. Мы также проверяем композиты как p , не имея возможности отличить их от простых чисел, но проверка пройдет так же долго, как и ее факторы.Наконец, отрицая
>2
к<3
и коммутацииTrue
/False
на выходе сохраняет байты, позволяя нам использоватьor
вместоand
.Соответствующая характеристика состоит в том, что делители 4n-1, взятые по модулю 12, имеют более 1 и 11, чем 5 и 7.
53 байта
Попробуйте онлайн!
источник
Python 2 , 52 байта
Попробуйте онлайн!
Выходы
True
/False
перевернутые. Использует эту характеристику:Мы проверяем,
8*n-2+3*b*b
является ли любой идеальным квадратом для любогоb
от1
доn+1
. Мы избегаем,b=0
потому что это дает ошибку для квадратного корня отрицательного значения когдаn==0
, но это не может повредить, потому чтоb
может работать только нечетное число .Сделано не рекурсивно:
Python 2 , 53 байта
Попробуйте онлайн!
источник
range
. Здесь это близко, потому чтоb>n+1
это длинный базовый случай и0in
короткий.R ,
4543 байта-2 байта благодаря Vlo
Попробуйте онлайн!
Я вполне уверен, что нам нужно проверить только первые
n
треугольные числа для этого; Грубая сила проверяет,n
находится ли попарная разница треугольных чисел и их троек.источник
scan()
n<-scan();n%in%outer(T<-cumsum(0:n),3*T,"-")
Желе , 10 байт
Монадическая ссылка, принимающая целое число и возвращающая истинное значение (непустой список) или ложное значение (пустой список).
Попробуйте онлайн! (нижний колонтитул выполняет представление Python, чтобы показать
[0]
результаты, как они есть)... или увидеть тестов (работает от 0 до 20 включительно)
Как?
Дано N, формирует первые N номеров треугольников, вычитает N из каждого, делит каждый результат на 3 и сохраняет все результаты, которые являются одним из первых N номеров треугольников.
источник
Пыть , 10 байт
Попробуйте онлайн!
Объяснение:
источник
ɐ-
делаетHaskell , 48 байтов
Попробуйте онлайн!
источник
a==1
.J , 22 байта
Попробуйте онлайн!
Прямой и несколько неудачный подход.
объяснение
источник
e.2,@(!-/3*!)[:i.2+]
e.2,@(!-/3*!)1+i.,]
возможноMATL , 12 байт
Выходы
1
для правды,0
для ложных.Попробуйте онлайн! Или проверьте все тестовые случаи .
Как это работает, с примером
Рассмотрим вход
6
источник
Рубин ,
65 57 5248 байтПопробуйте онлайн!
Вдохновленный ответом xnor на python
источник
Python 3 , 84 байта
Попробуйте онлайн!
источник
05AB1E , 11 байт
Попробуйте онлайн!
объяснение
Это основано на том факте, что число T является треугольным, если
8T+1
является нечетным совершенным квадратом.Мы начинаем со списка треугольников, которые можем обрезать, вычисляем возможные большие треугольники, основываясь на них, и проверяем, действительно ли он треугольный.
источник
Japt , 16 байт
Попробуй это | Проверьте все тесты
объяснение
альтернатива
Попытайся
источник
Добавить ++ , 36 байт
Попробуйте онлайн!
источник