¿Es este número triangular?

33

Reto

Dado un número entero positivo, determine si es un número triangular y, en consecuencia, genere uno de los dos valores constantes y distintos.

Definición

Un número triangular es un número que se puede expresar como la suma de enteros positivos consecutivos, comenzando en 1. También se pueden expresar con la fórmula n(n + 1) / 2, donde nhay algún entero positivo.

Casos de prueba

Verdad:

1
3
6
10
15
21
55
276
1540
2701
5050
7626
18915
71253
173166
222111
303031
307720
500500
998991

Falsy

2
4
5
7
8
9
11
16
32
50
290
555
4576
31988
187394
501500
999999

Reglas

  • Su entrada puede ser una función o un programa.
  • Puede suponer que la entrada es un entero positivo por debajo de 10 6 .
  • Debe elegir dos salidas constantes y distintas para distinguir las dos categorías.

Este es el , por lo que gana el código más corto en bytes en cada idioma.

ETHproducciones
fuente
1
Relacionado , relacionado .
ETHproductions
Relacionado
Shaggy
¿Por qué no incluiste cero?
Neil
1
@Neil Quería minimizar el número de posibles casos límite, y manejar cero es uno de ellos que sentí que no era demasiado importante. ¿Crees que hubiera sido mejor si hubiera que manejar el cero? (La respuesta de Jelly actualmente falla en cero, por ejemplo)
ETHproductions

Respuestas:

21

Haskell , 23 bytes

EDITAR:

  • -1 byte: @xnor se deshizo de paréntesis con a $.

Una función anónima que toma un Inty devuelve a Char.

La salida es '1'para números triangulares y '0'para otros.

(!!)$show.(10^)=<<[0..]

Pruébalo en línea!

  • Usar como ((!!)$show.(10^)=<<[0..]) 998991.
  • Genera los números 1, 10, 100, 1000, ..., los convierte en cadenas y los concatena. Luego indexa en la cadena infinita resultante

    "1101001000100001000001000000...
Ørjan Johansen
fuente
66
¡Un método imaginativo! Puede guardar un byte con (!!)$show.(10^)=<<[0..].
xnor
20

Python , 24 bytes

lambda n:(8*n+1)**.5%1>0

Pruébalo en línea!

Salidas Falsepara números triangulares, Truepara el resto. Comprueba si 8*n+1es un cuadrado perfecto. Python tomará cuadrados perfectos para calcular flotantes enteros sin importar cuán grande sea, por lo que no hay problemas de coma flotante.

xnor
fuente
3
(1<<10000)**.5: OverflowError: int demasiado grande para convertir a flotante
isaacg
@isaacg El desafío no requiere entradas tan grandes: "Puede suponer que la entrada es un entero positivo por debajo de 10 ^ 6"
trichoplax
1
@trichoplax Creo que estaba disputando la afirmación de xnor en el texto. La presentación está bien, estoy de acuerdo.
isaacg
13

Jalea , 4 bytes

R+\ċ

Pruébalo en línea!

¿Cómo?

R+\ċ - Main link: n
R    - range(n)   -> [1,2,3,...,N]
  \  - cumulative reduce by:
 +   -   addition -> [1,3,6,...,T(N)]
   ċ - count occurrences of right (n) in left -> 1 if triangular, 0 otherwise
Jonathan Allan
fuente
Me sorprende que la reducción acumulativa no realice automáticamente un rango. ¿Hay una opción de diseño detrás de esto?
ETHproductions
No estoy 100% seguro, pero creo que sería necesario (al menos en la actualidad) que la operación diádica se redujera y causaría un rango.
Jonathan Allan
... en realidad, incluso eso no parece aplicarse (por ejemplo, esto frente a esto . Parece que la implementación de enlace rápido anula de tal manera que el iterable no hace un rango, incluso si la operación diádica lo define para un argumento. Pinned Dennis al campo este :)
Jonathan Allan
@ETHproductions /y \probablemente se encontraban entre los primeros cinco rápidos que se implementaron, anterior a la idea de lanzar argumentos enteros al rango.
Dennis
13

Retina , 10 bytes

(^1|1\1)+$

La entrada está en unario. La salida es 0o 1.

Pruébalo en línea! (Como un conjunto de pruebas que realiza la conversión de decimal a unario por conveniencia).

Explicación

Este es el ejercicio más básico en referencias directas. La mayoría de las personas están familiarizadas con las referencias inversas en expresiones regulares, por ejemplo, (.)\1para que coincida con un carácter repetido. Sin embargo, algunos de los sabores más avanzados le permiten utilizar una referencia inversa antes o dentro del grupo al que se refiere. En ese caso, generalmente se denomina referencia directa. Esto puede tener sentido si la referencia se repite. Puede que no esté bien definido en la primera iteración, pero en las iteraciones posteriores, el grupo posterior o circundante ha capturado algo y puede reutilizarse.

Esto se usa más comúnmente para implementar patrones recurrentes en cadenas unarias. En este caso, intentamos hacer coincidir la entrada como la suma de enteros consecutivos:

(        # This is group 1, which we'll repeat 1 or more times.
  ^1     #   Group 1 either matches a single 1 at the beginning of the string.
|        # or
  1\1    #   It matches whatever the previous iteration matched, plus another
         #   1, thereby incrementing our counter.
         # Note that the first alternative only works on the first iteration
         # due to the anchor, and the second alternative only works *after*
         # the first iteration, because only then the reference is valid.
)+
$        # Finally, we make sure that we can exactly hit the end of the
         # string with this process.
Martin Ender
fuente
1
¿Por qué no (^|1\1)+$funciona?
Leaky Nun
3
Los motores de expresión regular @LeakyNun tienen una optimización de que dejan de repetir un grupo si estaba vacío n veces donde n es el mínimo del cuantificador que está utilizando (en su caso 1; si el mínimo era 0, se intentaría una vez de todos modos) . Si cambia el +a {2,}, debería funcionar. Esta optimización evita bucles infinitos, pero también es lo único que evita que la expresión regular de .NET se complete por sí sola.
Martin Ender
Esto me ahorró 70 bytes: codegolf.stackexchange.com/a/118387
Neil
¡Haz 74 bytes, gracias a \G!
Neil
8

Mathematica, 16 bytes

OddQ@Sqrt[1+8#]&

Esencialmente un puerto de la solución Python de xnor . Salidas Truepara números triangulares, de lo Falsecontrario.

ngenisis
fuente
7

JavaScript (ES6), 30 27 bytes

Guardado 2 bytes gracias a kamoroso94

f=(n,k)=>n>0?f(n+~k,-~k):!n

Casos de prueba

Versión no recursiva (ES7), 19 bytes

La respuesta del puerto de Adnan .

x=>(8*x+1)**.5%1==0
Arnauld
fuente
Solo viendo ahora que editó la solución de 19 bytes en su respuesta unos minutos antes de que publique la mía . ¿Debo eliminar el mío? ¿Cuál es la etiqueta generalmente aceptada en eso?
Shaggy
1
@ Shaggy No creo que sea un problema real aquí. Mi respuesta 'principal' realmente es la recursiva.
Arnauld
Reducir a 28 bytes con f=(n,k=1)=>n>0?f(n-k,k+1):!n?
kamoroso94
1
@ kamoroso94 ¡Gracias! Actualizado. Y se guardó un tercer byte al omitir la inicialización de k.
Arnauld
Uso elegante de NO a nivel de bit como un incrementador para un undefinedvalor inicial ; fue un placer leer su edición después de que llegué independientemente a su solución anterior.
apsillers
6

CJam , 11 bytes

ri2*_mQ_)*=

Salidas 1para triangular, de lo 0contrario.

Pruébalo en línea!

Explicación

Considere la entrada 21.

ri               e# Input integer.             STACK: 21
  2*             e# Multiply by 2.             STACK: 42
    _            e# Duplicate.                 STACK: 42, 42
     mQ          e# Integer square root.       STACK: 42, 6
       _)        e# Duplicate, increment.      STACK: 42, 6, 7
         *       e# Multiply.                  STACK: 42, 42
          =      e# Equal?                     STACK: 1
Luis Mendo
fuente
6

Brain-Flak , 40 bytes

(([{}](((()))<>))<>){<>({}({}({})))}{}{}

Wheat Wizard y yo tuvimos un duelo sobre esta pregunta. Cuando decidimos publicar nuestras soluciones, estábamos atados a 42 bytes, pero encontré un golf de 2 bytes de su solución. Decidimos que contaría como el desempate (mi solución está a continuación).

Pruébalo en línea!

Explicación:

# Set up the stacks like this:  -input
                                     1     -input
                                     1          1
(([{}](((()))<>))<>)                 ^

# Output 1 for triangular and 0 for non-triangular 
{<>({}({}({})))}{}{}

Para obtener una explicación completa, consulte la respuesta de Wheat Wizard .


Brain-Flak , 42 bytes

(([({})])<>){(({}())<>{}({})){((<>))}{}{}}

Salidas 0\n(nueva línea literal) para verdadero, y la cadena vacía para falso.

La idea es restar 1, luego 2 y luego 3 hasta la entrada. Si presiona 0, entonces sabe que este es un número triangular, por lo que puede detenerse allí.

Pruébalo en línea! (verdad)
Pruébalo en línea! (falso)

# Push -input on both stacks. One is a counter and the other is a running total
(([({})])<>)

# Count up from -input to 0
{
  # Push the new total which is: (counter += 1) + total (popped) + input (not popped)
  # This effectively adds 1, then 2, then 3 and so on to the running total
  (({}())<>{}({}))
  # If not 0
  {
    # Push to 0s and switch stacks to "protect" the other values
    ((<>))
  # End if
  }
  # Pop the two 0s, or empty the stack if we hit 0
  {}{}
# End loop
}

Aquí hay una solución de 46 bytes que me pareció interesante.

{<>(({}())){({}[()]<>{(<({}[()])>)}{}<>)}{}<>}

Salidas 0\n(nueva línea literal) para verdadero, la cadena vacía para falso.

La idea es contar desde la entrada por números consecutivos, 1 a la vez. Por ej input - (1) - (1,1) - (1,1,1). Cada vez que restamos, si aún no estamos en 0, dejamos un valor adicional en la pila. De esa manera, si estamos en 0 y seguimos restando cuando explotamos, eliminamos el último valor en la pila. Si la entrada fue un número triangular, terminaremos exactamente en 0 y no resaltaremos el 0.

Pruébalo en línea! Truthy
Pruébalo en línea! falso

# Implicit input (call it I)

# Until we reach 0, or the stack is empty
{
  # Add 1 to the other stack and push it twice. This is our counter.
  <>(({}()))
  # While counter != 0
  {
    # counter -= 1
    ({}[()]
    # if I != 0 
    <>{
      # I -= 1, and push 0 to escape the if
      (<({}[()])>)
    # End if
    }
    # Pop from the stack with I. This is either the 0 from the if, or I
    {}
    # Get ready for next loop End while
    <>)
  # End While
  }
  # Pop the counter that we were subtracting from
  {}<>
# End Until we reach 0, or the stack is empty.
}
Riley
fuente
6

Jalea , 5 bytes

×8‘Ʋ

Pruébalo en línea!

Fondo

Deje n ser la entrada. Si n es el k número triangular, tenemos

norte=k(k+1)2k2+k-2norte=0 0k=12(-1±1+8norte),

lo que significa que habrá una solución natural si y solo si 1 + 8n es un cuadrado perfecto y extraño. Claramente, no se requiere verificar la paridad de 1 + 8n .

Cómo funciona

×8‘Ʋ  Main link. Argument: n

×8     Yield 8n.
  ‘    Increment, yielding 8n + 1.
   Ʋ  Test if the result is a perfect square.
Dennis
fuente
5

PowerShell , 31 30 bytes

"$args"-in(1..1e6|%{($s+=$_)})

Pruébalo en línea!

Agradable y lento método de fuerza bruta. Haga una matriz de cada suma de 1 a 10 6 , y vea si el argumento está ahí.

briantista
fuente
5

Brain-Flak , 42 bytes

(([{}](<((())<>)>))<>){<>({}({}({})))}{}{}

Pruébalo en línea!

Explicación

El objetivo de este programa es crear un estado en dos pilas y realizar una operación constante en ambas pilas hasta que uno de ellos sea cero, entonces podemos generar resultados dependiendo de en qué pila nos encontremos. Esto es similar a los programas que determinan el signo de un número. Estos programas colocan nen una pila y -nen la otra y agregan una y cambian las pilas hasta que una de las pilas sea cero. Si el número fue negativo en primer lugar, la primera pila llegará a cero, si el número fue positivo, la otra pila llegará a cero.

Aquí creamos dos pilas, una que resta números consecutivos de la entrada y otra que solo resta uno. El que resta números consecutivos solo terminará si el número es triangular (de lo contrario, simplemente pasará cero y seguirá en los negativos). El otro siempre terminará para cualquier número positivo, pero siempre lo hará más lento que el primero, por lo que los números no triangulares terminarán en esa pila.

Entonces, ¿cómo configuramos pilas para que la misma operación reste números consecutivos en uno y reste uno en el otro? En cada pila tenemos la entrada en la parte superior para que pueda verificarse, debajo tenemos la diferencia y debajo tenemos la diferencia de la diferencia. Cada vez que corremos agregamos la "diferencia de la diferencia" a la "diferencia" normal y la restamos de la entrada. Para la pila que verifica la triangularidad, establecemos nuestra doble diferencia para 1que obtengamos enteros consecutivos cada vez que corremos, para la otra pila la configuramos para 0que nunca cambiemos la diferencia, es decir, siempre permanece 1. Aquí está cómo se configura la pila al principio, dónde nestá la entrada:

-n  -n
 0   1
 1   0

Cuando finalmente terminamos, podemos usar estas diferencias para verificar en qué pila estamos, sacamos los dos valores superiores y obtenemos 1un número triangular y 0un número no triangular.


Código anotado

(([{}](<((())<>)>))<>) Set up the stack
{                      While
 <>                    Switch stacks
 ({}({}({})))          Add bottom to second to bottom, add second to bottom to top
}                      End while
{}{}                   Pop the top two values

Aquí hay una solución de 50 bytes que también me gusta.

{(({}[()]))}(([[]])<>){({}{}())<>}({}{()<><{}>}{})

Pruébalo en línea!

Asistente de trigo
fuente
5

Cubix , 23 24 25 bytes

I1Wq/)s.;0..s;p-?\.+O@u

0 para veracidad y nada 0 para falsey. Fuerzas brutas incrementando el contador, sumando a la suma acumulativa y comparando con la entrada. Ahora intenta colocarlo en un cubo de 2x2x2. ¡Lo hizo!

    I 1
    W q
/ ) s . ; 0 . .
s ; p - ? \ . +
    O @
    u .

Pruébalo en línea!

  • / Reflexiona para enfrentar.
  • I10\ obtener entrada entera, presionar 1 (contador), presionar 0 (suma) y reflejar
  • +s;p-cuerpo de bucle Agregue suma y contador, suelte la suma anterior, aumente la entrada y reste
  • ? Prueba el resultado de la resta
    • Para obtener 0 resultados, continuar recto \.uO@refleja la cara inferior, sin operación, giro en U, salida y alto.
    • Para obtener un resultado positivo, gire a la derecha en la cara inferior y @deténgase
    • Para obtener un resultado negativo, gire la ;qWs)/suresta de caída a la izquierda , coloque la entrada en la parte inferior, cambie a la izquierda, cambie el contador y la suma, incremente el contador, refleje, cambie la suma y el contador, gire en U en el cuerpo del bucle principal.
MickyT
fuente
Tan tentadoramente cerca ... ese último byte requerirá mucho esfuerzo e inteligencia.
ETHproductions
Sí, pensé que lo tenía pero está siendo evasivo
MickyT
1
@ETHproductions encontró el byte
MickyT
Su código y su cubo desplegado parecen ser diferentes, la esquina inferior derecha está .en el cubo pero 1en su código.
Wheat Wizard
@WheatWizard Gracias por eso, mala edición de mi parte
MickyT
4

05AB1E , 7 6 bytes

EDITAR : Gracias a @Dennis: guardé un byte porque olvidé el operador de incremento

8*>t.ï

Pruébalo en línea!

nes triangular si sqrt(8n + 1)es un número entero

Cómo funciona

8* # multiply implicit input by 8
  > # add one
   t # sqrt
    .ï # is integer
Neil A.
fuente
Probablemente aún no estaba disponible en ese momento, pero t.ïpuede estarlo en Ųestos días, lo cual es una opción para verificar si un número es un cuadrado.
Kevin Cruijssen
4

Perl 6 , 17 bytes

{$_∈[\+] 1..$_}

Simplemente verifica si $_, la entrada a la función, es igual a cualquiera de los elementos de la reducción de suma triangular (1, 1+2, ..., 1+2+...+$_).

Sean
fuente
4

Alicia , 38 22 bytes

Muchos bytes guardados gracias a Martin y Leo

/ i \ 2 * .2RE.h * -n / o @

Hay una nueva línea final. Salidas 1para triangular, de lo 0contrario.

Pruébalo en línea!

Explicación

Utiliza el mismo enfoque que mi respuesta de CJam , solo que más torpe. En forma linealizada, el programa se convierte

i2*.2RE.h*-no@

donde el iy oestán realmente en modo ordinal.

Considere la entrada 21como un ejemplo.

i         Input integer                       STACK: 21
2*        Multiply by 2                       STACK: 42
.         Duplicate                           STACK: 42, 42
2RE       Integer square root                 STACK: 42, 6
.         Duplicate                           STACK: 42, 6, 6
h         Increment                           STACK: 42, 6, 7
*         Multiply                            STACK: 42, 42
-         Subtract                            STACK: 0
n         Logical negation                    STACK: 1
o         Output integer                      STACK:
@         End program
Luis Mendo
fuente
Mi primera respuesta de Alice
Luis Mendo
1
Tengo la sensación de que esto podría reducirse a la mitad con una de las elegantes estructuras de control de Martin ...
ETHproductions
Yo también ... :-)
Luis Mendo
Mi primer golf de Alice: el mismo código, 23 bytes
Nitrodon
Un diseño más "estándar" para este tipo de programa sería esta . Dicho esto, puede deshacerse del 1 en la pila y simplemente generar la negación lógica de la resta (es decir ...h*-no@)
Leo
4

Japt , 10 7 bytes

Guardado 3 bytes gracias a @Luke y @ETHproductions

*8Ä ¬v1

Pruébalo en línea!

Explicación:

*8Ä ¬v1
    ¬    // Square root of:
*8       //   Input * 8
  Ä      //   +1
     v1  // Return 1 if divisible by 1; Else, return 0

õ å+ øU

Explicación:

õ å+ øU
õ           // Create a range from [1...Input]
  å+        // Cumulative reduce by addition
     øU     // Does it contain the input?

Pruébalo en línea!

Oliver
fuente
La pregunta pide dos salidas constantes distintas.
xnor
*8Ä ¬u1 cpara 9B (salidas 0 si la entrada es triangular, 1 de lo contrario)
Luke
@Luke Usted podría cambiar u1 ca v1, creo (conmutación de las salidas)
ETHproductions
7 bytes? ¡Agradable! De alguna manera me perdí esto mientras publicaba mi propia solución similar a fines del último día. Avíseme si desea que lo elimine.
Shaggy
4

R , 23 19 bytes

Enfoque similar al de otras respuestas. Comprueba si 8x+1es un cuadrado perfecto.
-4 bytes gracias Giuseppe y MickyT.

!(8*scan()+1)^.5%%1

Pruébalo en línea!

Robert S.
fuente
2
puedes usar en !lugar de==0
Giuseppe
¡Esto es extra agradable ya que también está vectorizado!
Giuseppe
1
Creo que también puedes deshacerte de los soportes exteriores!(8*scan()+1)^.5%%1
MickyT
3

MATL , 5 bytes

t:Ysm

Pruébalo en línea!

Explicación:

t       % Duplicate input
 :      % Range(1, input)
  Ys    % Cumulative sum. This will push the first *n* triangular numbers
    m   % ismember. Pushes true if the input is contained within the array we just pushed
DJMcMayhem
fuente
Iba a publicar t:Ys=a. Se olvidó de m:-)
Luis Mendo
1
@LuisMendo No lo supe mhasta que vi esta respuesta . Es curioso cómo las dos respuestas son casi idénticas: D
DJMcMayhem
3

Lote, 72 bytes.

@set/aj=i=0
:l
@if %1% gtr %j% set/aj+=i+=1&goto l
@if %1==%j% echo 1

Salidas 1 en caso de éxito, nada en caso de fracaso. También funciona para cero, aunque la pregunta no lo solicita por alguna razón.

Neil
fuente
3

JavaScript (ES7), 19 18 bytes

De mi respuesta a una pregunta relacionada .

Salidas falsepara números triangulares o trueno triangulares, según lo permitido por el OP.

n=>(8*n+1)**.5%1>0

Intentalo

f=
n=>(8*n+1)**.5%1>0
oninput=_=>o.innerText=f(+i.value)
<input id=i type=number><pre id=o>

Lanudo
fuente
Creo que podría guardar un byte con n=>(8*n+1)**.5%1>0(que revertiría las salidas)
ETHproductions
@ETHproductions: OK, siempre que lo permita. Sin embargo, ¿está permitido hacerlo normalmente?
Shaggy
1
Califica como "dos salidas constantes y distintas", así que sí. Sin embargo, otros desafíos de problemas de decisión pueden requerir veracidad / falsedad.
ETHproductions
3

PHP, 30 bytes

Imprime 1 para verdadero y nada para falso

<?=fmod(sqrt(8*$argn+1),2)==1;

Pruébalo en línea!

fmod

PHP, 37 bytes

Imprime 1 para verdadero y nada para falso

<?=($x=sqrt($q=2*$argn)^0)*$x+$x==$q;

Pruébalo en línea!

Jörg Hülsermann
fuente
3

Mathematica, 28 bytes

!Accumulate@Range@#~FreeQ~#&
J42161217
fuente
Recomiendo reemplazar 7!por #. Primero, es más corto; Más importante aún, la solución actual no es correcta, ya que impone artificialmente un límite en el tamaño de la entrada en la que trabaja.
Greg Martin
1
OP dice: "Puede suponer que la entrada es un número entero positivo por debajo de 10 ^ 6". Pero me gusta su idea y la tomaré, aunque la mía da el resultado correcto para cada caso usando una lista de 5040 elementos pero el peor de los casos. necesita una lista de 999999 elementos. ¡Gracias por la sugerencia!
J42161217
1
¡Vaya, lo siento, no vi el comentario del OP! Sí, hay algunos incentivos "perversos" en el golf de código: ese ahorro de 1 byte es más importante en una pregunta de golf de código que toda la eficiencia del mundo :)
Greg Martin
3

Sobresalir, 31 22 bytes

9 bytes guardados gracias a Octopus

Salidas TRUEpara números triangulares. De lo contrario FALSE. Comprueba si 8*n+1es un cuadrado perfecto.

=MOD(SQRT(8*B1+1),1)=0
Wernisch
fuente
1
=MOD(SQRT(8*A1+1),1)=0 ahorra algunos bytes
Pulpo
2

Brachylog , 5 bytes

≥ℕ⟦+?

Pruébalo en línea!

Explicación

≥ℕ⟦+?
≥ℕ     There is a number from 0 to {the input} inclusive
  ⟦    such that the range from 0 to that number
   +   has a sum
    ?  that equals the input

fuente
2

Python - 52 bytes

Nota: Sé que las otras dos respuestas de Python son mucho más cortas, pero esta es la forma de la vieja escuela, más un algoritmo manual

n=input();i=s=0
while s<n:s=(i*i+i)/2;i+=1
print s>n
Sr. Xcoder
fuente
2

APL (Dyalog) , 6 bytes

⊢∊+\∘

Pruébalo en línea!

Explicación

⊢∊+\∘
                       Creates a range from 1 to the right_argument
  +\                    Cumulative sum of this range; 1 1+2 1+2+3 .. 1+2+..+n. These are the triangular numbers
⊢∊                      Does the right argument belong to this list of integers in this cumulative sum

Salidas 0para falso y 1para verdadero.

Kritixi Lithos
fuente
2

TI-BASIC, 10 7 bytes

-3 gracias a @lirtosiast

:not(fPart(√(8Ans+1

Toma entrada en X. Comprueba si √(8X+1)es un número entero

Scott Milner
fuente
¿Por qué no not(fPart(√(8Ans+1?
lirtosiast
@lirtosiast Eso funcionará, ¡gracias!
Scott Milner