Este é um número triangular truncado?

20

Sequência OEIS relacionada: A008867

Número triangular truncado

Uma propriedade comum dos números triangulares é que eles podem ser organizados em um triângulo. Por exemplo, pegue 21 e organize em um triângulo de os:

     o 
    oo
   ooo
  oooo
 ooooo
oooooo

Vamos definir um "truncamento:" cortando triângulos do mesmo tamanho de cada canto. Uma maneira de truncar 21 é a seguinte:

     . 
    . .
   ooo
  oooo
 . ooo
. . oo. .

(Os triângulos de .são cortados do original).

Há 12 os restantes, então 12 é um número de triângulo truncado.

Tarefa

Seu trabalho é escrever um programa ou uma função (ou equivalente) que use um número inteiro e retorne (ou use qualquer um dos métodos de saída padrão) se um número é um número de triângulo truncado.

Regras

  • Sem brechas padrão.
  • A entrada é um número inteiro não negativo.
  • Um corte não pode ter um comprimento lateral superior à metade do triângulo original (ou seja, os cortes não podem se sobrepor)
  • Um corte pode ter comprimento lateral zero.

Casos de teste

Verdade:

0
1
3
6
7
10
12
15
18
19

Falsy:

2
4
5
8
9
11
13
14
16
17
20

Casos de teste para todos os números inteiros até 50: Link TIO

Isso é , então os envios com a menor contagem de bytes em cada idioma ganham!

JungHwan Min
fonte
1
Devemos produzir saídas verdadeiras e falsas ou dois valores consistentes estão ok?
Assistente de trigo
@WheatWizard dois valores consistentes são aceitáveis.
JungHwan Min
Por mais que os truncamentos se sobreponham, o resultado é equivalente a um triângulo menor com truncamentos menores (se os truncamentos puderem ter comprimento lateral 0).
Asone Tuhid

Respostas:

7

Haskell , 46 bytes

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

Experimente online!

Depois de lançar um monte de teoria dos números no problema (obrigado @flawr), encontrei esta caracterização:

n é um número triangular truncado exatamente se na fatoração primária de 4n-1 , qualquer primo da forma 5 mod 12 ou 7 mod 12 aparece um número par de vezes.

Isso significa, por exemplo, que 4n-1 pode não ser divisível por 5, a menos que seja divisível por 5 2 = 25 e o número total de 5 fatores é par.

Haskell não tem uma fatoração embutida, mas podemos improvisar. Se trabalharmos com fatorações em potências primas como 12 = 3 * 4 , podemos usar a instrução equivalente:

n é um número triangular truncado exatamente se a fatoração de 4n-1 em potências primárias não tiver termos de forma 5 mod 12 ou 7 mod 12 .

Podemos extrair a potência de um primo p aparecendo em k as gcd(p^k)k. Verificamos então que o resultado r não é 5 ou 7, módulo 12 como mod(r-5)12>2. Observe que r é ímpar. Também verificamos os compósitos como p , sem uma maneira de diferenciá-los dos números primos, mas a verificação passará enquanto seus fatores o fizerem.

Finalmente, negando >2para <3e comutação True/ Falsena saída salva um byte por nos deixar usar orem vez de and.


Uma caracterização relacionada é que os divisores de 4n-1 do módulo 12 têm mais 1 e 11 totais do que 5 e 7.

53 bytes

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

Experimente online!

xnor
fonte
Explicação realmente agradável!
Anfibológico
6

Python 2 , 52 bytes

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

Experimente online!

Saídas True/ Falseinvertidas. Usa esta caracterização:

n é um número triangular truncado exatamente se 8n-2 tiver a forma a 2 -3b 2 para alguns números inteiros a, b .

Verificamos se algum 8*n-2+3*b*bé um quadrado perfeito para qualquer um bde 1até n+1. Evitamos b=0porque isso dá um erro para uma raiz quadrada de um negativo quando n==0, mas isso não pode prejudicar porque apenas o ímpar bpode funcionar.

Feito de forma não recursiva:

Python 2 , 53 bytes

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

Experimente online!

xnor
fonte
As soluções recursivas e não recursivas geralmente são tão competitivas entre si em python?
boboquack
@boboquack Geralmente, a solução recursiva vence por alguns bytes range. Aqui está próximo, porque b>n+1é um caso de base longo e 0incurto.
Xnor
5

R , 45 43 bytes

-2 bytes graças ao Vlo

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

Experimente online!

Tenho certeza de que precisamos apenas verificar os primeiros nnúmeros triangulares para isso; a força bruta verifica se nhá diferenças entre pares dos números triangulares e seus triplos.

Giuseppe
fonte
scan() n<-scan();n%in%outer(T<-cumsum(0:n),3*T,"-")
Vlo
@Vlo facepalm eu tenho o hábito de usar funções em todos os lugares ...
Giuseppe
E eu acabei de adquirir o hábito de usar <- assignment em vez de (n = scan ()) ... tsk tsk
Vlo
5

Gelatina , 10 bytes

0r+\ð_÷3f⁸

Um link monádico que aceita um número inteiro e retorna um valor verdadeiro (uma lista não vazia) ou um valor falsey (uma lista vazia).

Experimente online! (o rodapé executa a representação do Python para mostrar os[0]resultados como estão)
... ou vê uma suíte de testes (executa de 0 a 20 inclusive)

Quão?

Dado N, forma os primeiros números do triângulo N, subtrai N de cada um, divide cada resultado por 3 e mantém todos os resultados que são um dos primeiros números do triângulo 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
Jonathan Allan
fonte
4

Pyt , 10 bytes

Đř△Đ3*ɐ-Ƒ∈

Experimente online!

Explicação:

        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
fonte
Você me venceu também, +1 GG
FantaC
@tfbninja Eu gostaria de ter uma explicação mais agradável para o que ɐ-faz
mudkip201
1
adicionado, você pode reverter, se quiser
FantaC
3

Haskell , 48 bytes

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

Experimente online!

Assistente de Trigo
fonte
Parece que seu cheque está com vista a==1.
Xnor
@ xnor vejo o porquê. Foi corrigido agora.
Assistente de trigo
3

J , 22 bytes

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

Experimente online!

Abordagem direta e um pouco mal praticada.

Explicação

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?
Cole
fonte
e.2,@(!-/3*!)[:i.2+]
precisa saber é o seguinte
e.2,@(!-/3*!)1+i.,]talvez
FrownyFrog
3

MATL , 12 bytes

tQ:qYst!3*-m

Saídas 1para verdade, 0para falsidade.

Experimente online! Ou verifique todos os casos de teste .

Como funciona, com exemplo

Considere entrada 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
Luis Mendo
fonte
1

05AB1E , 11 bytes

ÅT3*+8*>ŲZ

Experimente online!

Explicação

Å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

Isso se baseia no fato de que um número T é triangular se 8T+1for um quadrado perfeito ímpar.
Começamos na lista de triângulos que poderíamos truncar, calculamos os possíveis triângulos maiores com base neles e verificamos se é de fato triangular.

Emigna
fonte
1

Japonês , 16 bytes

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

Experimente | Verifique todos os casos de teste


Explicação

                     :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

Alternativo

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

Tente

Shaggy
fonte