Это усеченное треугольное число?

20

Связанная последовательность OEIS: A008867

Усеченное треугольное число

Общим свойством треугольных чисел является то, что они могут быть расположены в виде треугольника. Например, возьмите 21 и расположите в треугольник os:

     о 
    оо
   ооо
  оооо
 ооооо
оооооо

Давайте определим «усечение»: разрезание треугольников одинакового размера с каждого угла. Один из способов усечь 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

Это , поэтому выигрыши с кратчайшим количеством байтов на каждом языке!

Юнг Хван Мин
источник
1
Должны ли мы выводить правдивые и ложные результаты или два последовательных значения в порядке?
Wheat Wizard
@WheatWizard допустимы два последовательных значения.
JungHwan Мин
Сколько бы усечения не перекрывалось, результат эквивалентен меньшему треугольнику с меньшими усечениями (если усечения могут иметь длину стороны 0).
Asone Tuhid

Ответы:

7

Haskell , 46 байтов

f n=or[mod(gcd(p^n)(4*n-1)-5)12<3|p<-[1..4*n]]

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

Бросив кучу теории чисел в проблему (спасибо @flawr), я нашел эту характеристику:

n является усеченным треугольным числом, если в простой разложении 4n-1 любое простое число вида 5 mod 12 или 7 mod 12 появляется четное число раз.

Это означает, например, что 4n-1 может не делиться на 5, если он не делится на 5 2 = 25, а общее число 5 факторов является четным.

В Haskell нет встроенной факторизации, но мы можем импровизировать. Если мы работаем с факторизациями в простые числа типа 12 = 3 * 4 , мы можем использовать эквивалентное утверждение:

n является усеченным треугольным числом, в точности, если разложение 4n-1 в простые степени не имеет членов вида 5 mod 12 или 7 mod 12 .

Мы можем извлечь степень простого числа 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 байта

f n=sum[abs(mod k 12-6)-3|k<-[1..4*n],mod(4*n)k==1]<0

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

XNOR
источник
Действительно хорошее объяснение!
Амфибология
6

Python 2 , 52 байта

f=lambda n,b=1:b>n+1or(8*n-2+3*b*b)**.5%1>0<f(n,b+1)

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

Выходы True/ Falseперевернутые. Использует эту характеристику:

п является усеченным треугольное число точно , если 8n-2 имеет вид 2 -3b 2 для некоторых целых а, б .

Мы проверяем, 8*n-2+3*b*bявляется ли любой идеальным квадратом для любого bот 1до n+1. Мы избегаем, b=0потому что это дает ошибку для квадратного корня отрицательного значения когда n==0, но это не может повредить, потому что bможет работать только нечетное число .

Сделано не рекурсивно:

Python 2 , 53 байта

lambda n:0in[(8*n-2+3*b*b)**.5%1for b in range(~n,0)]

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

XNOR
источник
Являются ли рекурсивные и нерекурсивные решения настолько конкурентоспособными друг с другом в Python?
Boboquack
@boboquack Обычно рекурсивное решение выигрывает на несколько байтов range. Здесь это близко, потому что b>n+1это длинный базовый случай и 0inкороткий.
xnor
5

R , 45 43 байта

-2 байта благодаря Vlo

(n=scan())%in%outer(T<-cumsum(0:n),3*T,"-")

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

Я вполне уверен, что нам нужно проверить только первые nтреугольные числа для этого; Грубая сила проверяет, nнаходится ли попарная разница треугольных чисел и их троек.

Giuseppe
источник
scan() n<-scan();n%in%outer(T<-cumsum(0:n),3*T,"-")
Vlo
@Vlo facepalm У меня появилась привычка использовать функции везде ...
Джузеппе
И я просто вошел в привычку использовать <- присваивание вместо (n = scan ()) ...
tsk tsk
5

Желе , 10 байт

0r+\ð_÷3f⁸

Монадическая ссылка, принимающая целое число и возвращающая истинное значение (непустой список) или ложное значение (пустой список).

Попробуйте онлайн! (нижний колонтитул выполняет представление Python, чтобы показать[0]результаты, как они есть)
... или увидеть тестов (работает от 0 до 20 включительно)

Как?

Дано N, формирует первые N номеров треугольников, вычитает N из каждого, делит каждый результат на 3 и сохраняет все результаты, которые являются одним из первых N номеров треугольников.

0r+\ð_÷3f⁸ - Link: integer, N             e.g. 7
0r         - zero inclusive range N            [    0, 1, 2,   3,    4, 5,   6,   7]
  +\       - cumulative reduce with addition   [    0, 1, 3,   6,   10,15,  21,  28]
    ð      - start a new dyadic link with that, t, on the left and N on the right
     _     - t subtract N (vectorises)         [   -7,-6,-3,  -1,    3, 8,  14,  21]
      ÷3   - divivde by three (vectorises)     [-2.33,-2,-1.33,-0.33,1,2.67,4.67, 7]
         ⁸ - chain's left argument, t          [    0, 1, 3,   6,   10,15,  21,  28]
        f  - filter keep                       [                     1             ]
                                               - a non-empty list, so truthy
Джонатан Аллан
источник
4

Пыть , 10 байт

Đř△Đ3*ɐ-Ƒ∈

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

Объяснение:

        Implicit input
Đ       Duplicate input
ř       Push [1,2,...,input]
△       For each element k in the array, get the kth triangle number
Đ       Duplicate the top of the stack
3*      Multiply by 3
ɐ       ɐ - All possible:
 -                       subtractions between elements of the two arrays  
Ƒ       Flatten the nested array
∈       Is the input in the array
mudkip201
источник
Ты тоже меня обыграл, +1 ГГ
FantaC
@tfbninja Хотелось бы, чтобы у меня было более приятное объяснение того, что ɐ-делает
mudkip201
1
добавил, что вы можете откатить, если хотите, хотя
FantaC
3

Haskell , 48 байтов

f a|u<-[0..a]=or[x^2+x-3*(y^2+y)==2*a|x<-u,y<-u]

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

Мастер пшеницы
источник
Похоже, ваш чек с видом a==1.
xnor
@xнор понятно почему. Это было исправлено сейчас.
Пшеничный волшебник
3

J , 22 байта

e.[:,@(-/3*])2![:i.2+]

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

Прямой и несколько неудачный подход.

объяснение

e.[:,@(-/3*])2![:i.2+]
             2![:i.2+]  Range of triangular numbers up to N
      (-/3*])           All possible subtractions of 3T from T 
                        where T is triangular up to the Nth triangular number
    ,@                  Flattened into a single list
e.                      Is N in the list?
капуста
источник
e.2,@(!-/3*!)[:i.2+]
FrownyFrog
e.2,@(!-/3*!)1+i.,]возможно
FrownyFrog
3

MATL , 12 байт

tQ:qYst!3*-m

Выходы 1для правды,0 для ложных.

Попробуйте онлайн! Или проверьте все тестовые случаи .

Как это работает, с примером

Рассмотрим вход 6

t      % Implicit input. Duplicate
       % STACK: 6, 6
Q:q    % Increase, range, decrease element-wise. Gives [0 1 ... n]
       % STACK: 6, [0 1 ... 6]
Ys     % Cumulative sum
       % STACK: 6, [0 1 3 6 10 15]
t!     % Duplicate, transpose
       % STACK: 6, [0 1 3 6 10 15], [0;
                                     1;
                                     3;
                                     6;
                                     10;
                                     15]
3*     % Times 3, element-wise
       % STACK: 6, [0 1 3 6 10 15 21 28 36 45 55], [0;
                                                    3;
                                                    9;
                                                    18;
                                                    30;
                                                    45]
-      % Subtract, element-wise with broadcast
       % STACK: 6, [  0   1   3   6  10  15  21;
                     -3  -2   0   3   7  12  18;
                     -9  -8  -6  -3   1   6  12;
                    -18 -17 -15 -12  -8  -3   3;
                    -30 -29 -27 -24 -20 -15  -9;
                    -45 -44 -42 -39 -35 -30 -24;
                     -63 -62 -60 -57 -53 -48 -42]
m      % Ismember. Implicit display
       % STACK: 1
Луис Мендо
источник
1

05AB1E , 11 байт

ÅT3*+8*>ŲZ

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

объяснение

ÅT            # get a list of triangle numbers upto input
  3*          # multiply each by 3
    +         # add input to each
     8*       # multiply each by 8
       >      # increment each
        Ų    # check each for squareness
          Z   # max

Это основано на том факте, что число T является треугольным, если 8T+1является нечетным совершенным квадратом.
Мы начинаем со списка треугольников, которые можем обрезать, вычисляем возможные большие треугольники, основываясь на них, и проверяем, действительно ли он треугольный.

Emigna
источник
1

Japt , 16 байт

ò å+ d@Zd_-3*X¶U

Попробуй это | Проверьте все тесты


объяснение

                     :Implicit input of integer U
ò                    :Range [0,U]
  å+                 :Cumulative reduction by addition
     d@              :Does any X in array Z return true when passed through this function?
       Zd_           :  Does any element in Z return true when passe through this function?
          -3*X       :    Subtract 3*X
              ¶U     :    Check for equality with U

альтернатива

ò å+ £Zm-3*XÃdøU

Попытайся

мохнатый
источник