Secuencia H de Hofstadter

15

Definición

  • a(0) = 0
  • a(n) = n-a(a(a(n-1))) para entero n > 0

Tarea

Dado entero no negativo n, salida a(n).

Casos de prueba

n     a(n)
0     0
1     1
2     1
3     2
4     3
5     4
6     4
7     5
8     5
9     6
10    7
11    7
12    8
13    9
14    10
15    10
16    11
17    12
18    13
19    13
20    14
10000 6823

Referencias

Monja permeable
fuente
Desafíos relacionados con las secuencias de Hofstadter: 1 , 2 , 3
Martin Ender
44
Y sigo pensando que deberías hacer referencia a GEB ...
Martin Ender
1
¿Cómo es relevante la teoría de números aquí?
flawr
1
@flawr facepalm Déjame intentarlo de nuevo: Gödel, Escher, Bach: An Eternal Golden Braid
Stig Hemmer
1
@StigHemmer En realidad, Facepalm tiene su propio Emoji ahora: 🤦
Tobias Kienzler

Respuestas:

20

Haskell 23 22 bytes

f 0=0
f n=n-f(f$f$n-1)

Simplemente usa la definición de la secuencia. f(f$f$n-1)es equivalente a f (f (f (n-1))).

Prueba:

main = putStrLn . show $ map f [0..20]
-- => [0,1,1,2,3,4,4,5,5,6,7,7,8,9,10,10,11,12,13,13,14]

¡Gracias a Anders Kaseorg por un byte!

Perilla de la puerta
fuente
(f$f$f$n-1)= f(f$f$n-1)guarda un byte.
Anders Kaseorg
9

Jalea , 8 bytes

’ßßßạµṠ¡

Pruébalo en línea! o verificar los casos de prueba más pequeños .

Cómo funciona

’ßßßạµṠ¡  Main link. Argument: n

     µṠ¡  Execute the preceding chain sign(n) times.
’         Decrement n, yielding n - 1.
 ßßß      Recursively call the main link thrice.
    ạ     Take the absolute difference of n and the result.
Dennis
fuente
99
¿Puede el analizador Jelly manejar incluso programas de más de 10 bytes?
steenbergh
9

Mathematica, 20 bytes

El recuento de bytes asume la codificación ISO 8859-1 (o compatible) y se $CharacterEncodingestablece en un valor coincidente, como el valor predeterminado de Windows WindowsANSI.

±0=0
±n_:=n-±±±(n-1)

Esto define un operador unario ±.

Martin Ender
fuente
¿Explicarías qué hace o cómo funciona? Por cierto, felicidades por 100k.
DavidC
1
@DavidC Gracias. :) Es solo un operador incorporado que es la abreviatura de la función no utilizada PlusMinus. Ver esta publicación para más detalles.
Martin Ender
1
Muy interesante. Prescindir de la @o [ ]también.
DavidC
9

J, 14 12 bytes

-$:^:3@<:^:*

Guardado 2 bytes gracias a @ Leaky Nun .

Calcula el resultado llamándose recursivamente cuando n > 0 tres veces en n -1 y restando ese resultado de n . Hay una situación diferente para el caso base cuando n = 0. Allí se calcula n - n que es igual a 0.

a(n) = n - n = 0           if n = 0
       n - a(a(a(n-1)))    if n > 0

Pruébalo aquí.

Explicación

-$:^:3@<:^:*  Input: n
           *  Get the sign of n (n = 0 => 0, n > 0 => 1)
         ^:   Execute that many times
                (0 times means it will just be an identity function)
       <:       Decrement n
 $:             Call itself recursively
   ^:3          three times
      @         on n-1
-             Subtract that result from n and return
millas
fuente
No creo que se necesiten los paréntesis.
Leaky Nun
6

Julia, 16 bytes

!n=n>0&&n-!!!~-n

Pruébalo en línea!

Cómo funciona

Redefinimos el operador unario !para nuestros fines.

Si n = 0 , la comparación n>0devuelve falso y también lo hace !.

De lo contrario, el código después &&se ejecuta. ~-nes equivalente al (n-1)complemento de dos, !!!recursivamente llama !tres veces en n - 1 , y el valor resultante se resta de n .

Dennis
fuente
¿Te importaría agregar una explicación? No tengo idea de lo que está pasando con -!!~-._.
Downgoat
1
Nada sofisticado. !es simplemente el nombre de la función.
Dennis
5

Python, 31 bytes

a=lambda n:n and n-a(a(a(n-1)))

El límite de recursión y las limitaciones de tiempo hacen que la función anterior no sea práctica, pero en teoría debería funcionar (y funciona para n pequeña).

orlp
fuente
4

JavaScript (ES6), 52 bytes

n=>[0,...Array(n)].reduce((p,_,i,a)=>a[i]=i-a[a[p]])

Podría haber sido aburrido y haber escrito la versión recursiva, pero esta versión es mucho más rápida (maneja fácilmente el último caso de prueba) y también usa reduce eso es una ventaja!

Neil
fuente
3

CJam, 13 12 bytes

Gracias a Dennis por guardar 1 byte.

ri0{_(jjj-}j

Pruébalo aquí.

Martin Ender
fuente
Eso funciona para valores sorprendentemente altos. Creo que no necesitas el a.
Dennis
@ Dennis Oh, es bueno saberlo, gracias.
Martin Ender
3

R, 42 41 bytes

a=function(n)ifelse(n<1,0,n-a(a(a(n-1))))

Uso:

> a(1)
1
> a(10)
7

Sin embargo, este enfoque recursivo no escala bien para valores mayores de n.

DSkoog
fuente
Debería poder perder un byte (y varios errores con entradas incorrectas) si cambia su condición a n<1. Como es una secuencia, de todos modos solo se define realmente para enteros no negativos.
user5957401
a=function(n)"if"(n,n-a(a(a(n-1))),0)funcionará para varios bytes de descuento.
Giuseppe
3

Oasis , 6 bytes

Código:

nbaa-0

Versión ampliada:

a(n) = nbaa-
a(0) = 0

Código:

n      # Push n
 b     # Calculate a(n - 1)
  a    # Calculate a(a(n - 1))
   a   # Calculate a(a(a(n - 1)))
    -  # Subtract a(a(a(n - 1))) from n

Pruébalo en línea!

Adnan
fuente
2

Sesos , 58 55 bytes

0000000: 16e0d7 bdcdf8 8cdf1b e6cfbb 840d3f bf659b 38e187  ..............?.e.8..
0000015: f8639b 39dc37 fc893f 666c05 7e7ed9 b88b3f ae0d3f  .c.9.7..?fl.~~...?..?
000002a: 676ed8 bd9940 7fdc3b 36619e f1                    gn...@..;6a..

Maneja entradas de hasta 400 razonablemente bien, pero el tiempo de ejecución aumenta dramáticamente después de ese punto.

Pruébalo en línea! Verifique la depuración para ver el código SBIN generado.

Asamblea Sesos

El archivo binario anterior se generó al ensamblar el siguiente código SASM.

set numin, set numout

get
jmp
    jmp
        rwd 3, add 1, rwd 1, add 1, fwd 4, sub 1
    jnz
    rwd 3, sub 1
jnz
rwd 3, add 1, fwd 2
jmp
    rwd 1, sub 1, fwd 3, sub 1, fwd 2, add 3
    jmp
        rwd 2
        jmp
            rwd 3
        jnz
        fwd 6, get, rwd 4, sub 1
        jmp
            fwd 1, sub 1
            jmp
                rwd 3
            jnz
            sub 1
            jmp
                fwd 3
            jnz
            rwd 4, sub 1
        jnz
        fwd 1
        jmp
            rwd 1, add 1, fwd 1, add 1
        jnz
        sub 1, fwd 3, sub 1
        jmp
            fwd 3
        jnz
        rwd 1, sub 1
    jnz
    rwd 2, get
    nop
        rwd 3
    jnz
    fwd 3, get, rwd 2
    jmp
        fwd 2, add 1
        jmp
            fwd 3
        jnz
        rwd 1, add 1, rwd 2
        jmp
            rwd 3
        jnz
        fwd 1, sub 1
    jnz
    fwd 2
    jmp
        rwd 2, add 1, fwd 2, sub 1
    jnz
    nop
        get, fwd 3
    jnz
    rwd 1, add 1, fwd 2
jnz
rwd 2, sub 1
jmp
    rwd 1, sub 1, fwd 1, sub 1
jnz
rwd 1, put
Dennis
fuente
2

LISP, 61 bytes

(defun H(N)(if(= N 0)(return-from H 0)(- N(H(H(H(- N 1)))))))

Probablemente no sea la solución óptima, pero funciona.

Esteta
fuente
1

Java 7, 42 bytes

int c(int n){return n>0?n-c(c(c(n-1))):0;}

Sin golf y casos de prueba:

Pruébalo aquí.

class Main{
  static int c(int n){
    return n > 0
              ? n - c(c(c(n-1)))
              : 0;
  }

  public static void main(String[] a){
    for(int i = 0; i < 21; i++){
      System.out.println(i + ": " + c(i));
    }
    System.out.println("1000: " + c(1000));
  }
}

Salida:

0: 0
1: 1
2: 1
3: 2
4: 3
5: 4
6: 4
7: 5
8: 5
9: 6
10: 7
11: 7
12: 8
13: 9
14: 10
15: 10
16: 11
17: 12
18: 13
19: 13
20: 14
 (last case takes too long..)
Kevin Cruijssen
fuente
1

Rubí, 27 bytes

La implementación obvia.

a=->n{n<1?0:n-a[a[a[n-1]]]}

Esta es una respuesta más larga y rápida que almacena en caché las entradas anteriores de la secuencia. Ambas respuestas solo funcionan para versiones posteriores a 1.9, ya que fue cuando ->, la lambda stabby, fue presentada a Ruby.

->n{r=[0];i=0;(i+=1;r<<i-r[r[r[i-1]]])while i<n;r[n]}
Sherlock9
fuente
1

C #, 35 bytes

int a(int n)=>n>0?n-a(a(a(n-1))):0;
TheLethalCoder
fuente
1

Golfscript, 26 25 bytes

~ [0] {...., (=== \., @ - +} @ *) \;
~ [0] {...) \; == \., @ - +} @ *) \;

Pruébalo en línea!

Localmente 10000toma menos de medio segundo.

Monja permeable
fuente
1

C, 35 32 bytes

¡Guardado 3 bytes gracias a @PeterTaylor!

a(n){return n?n-a(a(a(n-1))):0;}

Pruébalo en Ideone!

Betseg
fuente
2
En C puede usar un número entero directamente como condicional, lo que permite un ahorro de tres bytes:a(n){return n?n-a(a(a(n-1))):0;}
Peter Taylor
1
@betseg: también tiene un :código erróneo . Deberías sacar el que está después ?.
owacoder
1

Javascript ES6, 22 bytes

a=n=>n&&n-a(a(a(n-1)))

Seré aburrido y haré la versión recursiva: P

Mama Fun Roll
fuente
1

VBA, 69 bytes

Function H(N):ReDim G(N):For j=1To N:G(j)=j-G(G(G(j-1))):Next:H=G(N)

Funciona en un abrir y cerrar de ojos en el conjunto de prueba, se ralentiza un poco por encima de n = 1000000, se encuentra con un muro de memoria un poco por encima de n = 25 millones.

Joffan
fuente
1

Pyth, 10 bytes

L-WbbyFtb3

Define una función y. Pruébelo en línea: demostración

Esto usa una característica relativamente nueva de Pyth. Puede aplicar una función varias veces utilizando la sintaxis de plegado. En realidad no guarda ningún byte, lo usé solo con fines de demostración.

Explicación:

L-WbbyFtb3
L            define function y(b), that returns:
    b           b
 -Wb            and subtract the following if b>0
     yF  3      y applied three times to
       tb       b - 1
Jakube
fuente
1

Arce, 28 26 bytes

`if`(n=0,0,n-a(a(a(n-1))))

Uso:

> a:=n->ifelse(n=0,0,n-a(a(a(n-1))));
> seq(a(i),i=0..10);
0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7
DSkoog
fuente
1

cc, 34 bytes

dsn[zdddd1-;a;a;a-r:aln!=L]dsLx;ap

La entrada se toma desde la parte superior de la pila. Este debe ser el único elemento en la pila, porque la profundidad de la pila se usa como contador. Ejemplo de uso:

$ dc
10000dsn[zdddd1-;a;a;a-r:aln!=L]dsLx;ap

Esta es una implementación bastante sencilla de la definición de secuencia:

dsn               # Store n as `n', and keep a copy as a depth buffer (see below)
[                 # Open loop definition
 z                # Push stack depth i for i-th term
 dddd             # Duplicate stack depth four times, for a total of five copies
 1-               # Get i-1 for use as index to previous term
                  #   Note that if we hadn't duplicated n above, or left something else
                  #   on the stack, 0-1 would be -1, which is not a valid array index
 ;a;a;a           # Fetch a(a(a(i-1)))
 -                # Calculate i-a(a(a(i-1)))
 r                # Arrange stack to store i-th term: TOS |  i  (i-a(a(a(i-1))))
 :a               # Store i-th term in array `a'
 ln!=L            # Load n. If n!=i, we're not done calculating terms yet, so execute loop
]                 # Close loop definition. Note that we started with five copies of i:
                  #   i-1 was used to get last term
                  #   i-a(...) was used to calculate current term
                  #   ... i :a was used to store current term
                  #   i ln !=L was used to check loop exit condition
                  # One copy of i is left on the stack to increment counter
dsLx              # Duplicate loop macro, store it, and execute copy
;a                # Last i stored on stack from loop will equal n, so use this to get a(n)
p                 # Print a(n)

De todos modos, comenzó de forma directa ... luego ocurrió el golf.

Joe
fuente
1

C ++ (MSVC, principalmente)

Versión normal: 40 bytes.

int a(int n){return n?n-a(a(a(n-1))):0;}

Versión de meta programación de plantilla: 130 bytes

#define C {constexpr static int a(){return
template<int N>struct H C N-H<H<H<N-1>::a()>::a()>::a();}};template<>struct H<0>C 0;}};

Uso:

std::cout << a(20) << '\n';       // Normal version
std::cout << H<20>::a() << '\n';  // Template version

La versión de la plantilla es el código más rápido, ya que no hay nada más rápido que mover un valor a un registro => con optimización, H<20>::a() compilar como:

mov esi, 14

Para 10000, la versión recursiva se bloquea debido a un error de desbordamiento de pila, y la versión de la plantilla se bloquea en tiempo de compilación debido a la profundidad de creación de instancias de la plantilla. GCC va a 900 (614)

HatsuPointerKun
fuente
Creo que no necesitas el espacio entre Cy {en la versión de meta programación de la plantilla
Zacharý
@ Zacharý MSVC se niega a compilar sin ese espacio
HatsuPointerKun
Ahh, ahora veo por qué eso parece seguir sucediendo
Zacharý
@ Zacharý Depende del tipo de macro. Si tiene parámetros, entonces puedo eliminar el espacio, pero aquí no los tiene
HatsuPointerKun
1

APL (Dyalog Unicode) , 18 17 bytes

{⍵=0:0⋄⍵-∇⍣3⊢⍵-1}

Pruébalo en línea!

Sorprendentemente, no hay una respuesta APL a este desafío. Esta es una implementación literal de la función en el OP.

TIO agota el tiempo de espera norte>90.

Guardado un byte gracias a @ Zacharý.

J. Sallé
fuente
1
{⍵=0:0⋄⍵-∇⍣3⊢⍵-1}
Zacharý
0

Python 3, 72 bytes

def f(n):
    a=[0];i=0
    while n:i+=1;a+=[i-a[a[a[i-i]]]];n-=1
    return a[i]

Ideone it!

Monja permeable
fuente
0

PowerShell v2 +, 56 bytes

$a={$n=$args[0];if($n){$n-(&$a(&$a(&$a($n-1))))}else{0}}

El equivalente de PowerShell de una lambda para formar la definición recursiva. Ejecútelo a través del &operador de llamada, por ejemplo &$a(5). Toma mucho tiempo tiempo en ejecutarse, incluso 50en mi máquina (un i5 reciente con 8GB de RAM) toma alrededor de 90 segundos.

Solución iterativa más rápida, 59 bytes.

param($n)$o=,0;1..$n|%{$o+=$_-$o[$o[$o[$_-1]]]};$o[-1]*!!$n

Más tiempo solo porque necesitamos tener en cuenta la entrada 0(eso es *!!$nal final). De lo contrario, simplemente construimos la matriz de forma iterativa $n, agregando un nuevo elemento cada vez, y enviamos el último al final $o[-1]. Súper rápido: el cálculo 10000en mi máquina demora aproximadamente 5 segundos.

AdmBorkBork
fuente
0

> <> , 55 + 2 = 57 bytes

^~n;
.~-]{:0$
v>1-}32[
v/  /:1-32[
>$:?/$~]{:0$.
/30@2[

Se espera que la entrada esté presente en la pila al inicio del programa, por lo que +2 bytes para el -vindicador. Pruébalo en línea!

Esto es muy lento, ya que utiliza la recursividad para calcular el resultado. Usando TIO, h(50)toma más de un minuto. Devuelve los resultados correctos <= 30, así que estoy seguro de que funcionará h(10000), ¡simplemente no lo he ejecutado para averiguarlo!

Sok
fuente