Función colombiana inversa

28

Definamos una secuencia: la secuencia de suma de n dígitos (n-DSS) es una secuencia que comienza con n . Si el último número fue k , entonces el siguiente número es k + suma de dígitos (k) . Aquí están los primeros n-DSS:

1-DSS: 1, 2, 4, 8, 16, 23, 28, 38, 49, 62, 70...
2-DSS: 2, 4, 8, 16, 23, 28, 38, 49, 62, 70, 77...
3-DSS: 3, 6, 12, 15, 21, 24, 30, 33, 39, 51, 57...
4-DSS: 4, 8, 16, 23, 28, 38, 49, 62, 70, 77, 91...
5-DSS: 5, 10, 11, 13, 17, 25, 32, 37, 47, 58, 71...
6-DSS: 6, 12, 15, 21, 24, 30, 33, 39, 51, 57, 69...
7-DSS: 7, 14, 19, 29, 40, 44, 52, 59, 73, 83, 94...
8-DSS: 8, 16, 23, 28, 38, 49, 62, 70, 77, 91, 101...
9-DSS: 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99...

Para 1, esto es A004207 , aunque los primeros dígitos son diferentes debido a una definición ligeramente diferente. Para 3, es A016052 ; para 9, A016096 .

El desafío de hoy es encontrar la secuencia de suma de n dígitos más baja en la que aparece un número dado. Esto se llama "función colombiana inversa" y es A036233 . Los primeros veinte términos, comenzando con 1 son:

1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 5, 3, 5, 7, 3, 1, 5, 9, 7, 20

Algunos otros buenos casos de prueba:

117: 9
1008: 918

Solo tiene que manejar enteros mayores que 0, y puede tomar entradas y salidas en cualquier formato estándar. Como de costumbre, este es el , por lo que gana la respuesta más corta en cada idioma.

DJMcMayhem
fuente
Relacionado
DJMcMayhem

Respuestas:

12

Haskell , 104 64 63 bytes

(-26 gracias a H.PWiz, adicional -14 gracias a Sriotchilism O'Zaic, -1 adicional gracias a cole)

Esta es una función.

f x=[y|y<-[1..],x==until(>=x)(foldr((+).read.pure)<*>show)y]!!0

Pruébalo en línea!


Explicación:

(foldr((+).read.pure)<*>show)

Secuencia de funciones compuestas que devuelve y + suma digital de y. Primero se convierte en cadena, luego hace gimnasia de mónada para obtener la suma de los personajes y el número original (gracias a Cole).

los <*> operador en este contexto tiene tipo y definición

(<*>) :: (a -> b -> c) -> (a -> b) -> c
f <*> g = \x -> f x (g x)

para que podamos escribir lo anterior como

\x -> foldr ((+) . read . pure) x (show x)

Esto read . pureconvierte a Charen un número, entonces(+) . read . pure :: Char -> Int -> Int agrega un dígito a un valor acumulado. Este valor se inicializa al número dado en el pliegue.

until (>=x) {- digital sum function -} y

untilaplica repetidamente una función a su resultado (en este caso, la suma digital y + y) hasta que cumpla un requisito especificado por una función en el primer argumento. Esto le da al elemento y-DSS más pequeño que es mayor o igual a x.

[y | y<-[1..]; x == {- smallest y-DSS element >= x -} ]

Lista perezosa infinita de y tal que el elemento y-DSS más pequeño> = x es en realidad x. Utiliza la notación de comprensión de la lista de Haskell (que también me había olvidado por completo, gracias a todos).

f x = {- aforementioned list -} !! 0

Primer elemento de esa lista, que es la y más pequeña que satisface el requisito del desafío.

Transformada de Fourier de Rin
fuente
1
Aquí es cómo se Jugamos al golf.
H.PWiz
1
@ H.PWiz Esto debería ser el mismo no? Creo que sí, pero su uso de fmapen primer lugar me confunde un poco.
Wheat Wizard
1
OK, tomó mucho esfuerzo pero abusé de la mónada del lector para eliminar un solo byte. Código de punto libre de Woohoo! TIO
cole
@ SriotchilismO'Zaic Cool. Acabo de jugar golf al código mecánicamente, sin pensarlo
H.PWiz
1
No estoy seguro de cómo editar la solicitud en el dispositivo móvil, así que acabo de editar una explicación de mi código; siéntase libre de cambiar o retroceder.
cole
4

Perl 6 , 44 bytes

->\a{+(1...{a∈($_,{$_+.comb.sum}...*>a)})}

Pruébalo en línea!

Solución ingenua que verifica cada secuencia hasta que encuentra una que contiene la entrada

Explicación:

->\a{                                    }  # Anonymous code block taking input as a
     +(1...{                           })   # Find the first number
            a∈(                       )     # Where the input is an element of
                                ...         # The sequence
               $_,                          # Starting with the current number
                  {            }   # Where each element is
                   $_+             # Is the previous element plus
                      .comb.sum    # The digit sum
                                   *>a      # Until the element is larger than the input
Jo King
fuente
3

MATL , 18 bytes

`@G:"ttFYAs+]vG-}@

Pruébalo en línea! O verifique los primeros 20 valores .

Explicación

Para la entrada i, esto sigue aumentando nhasta que se incluyan los primeros itérminos de la nenésima secuencia i. Es suficiente probar los itérminos para cada secuencia porque la secuencia está aumentando.

`         % Do...while
  @       %   Push iteration index, n. This is the firsrt term of the n-th sequence
  G:      %   Push [1 2 ... i], where i is the input
  "       %   For each (i.e., do the following i times)
    tt    %     Duplicate twice
    FYA   %     Convert to digits
    s     %     Sum
    +     %     Add to previous term. This produces a new term of the n-th sequence
  ]       %   End
  v       %   Concatenate all terms into a column vector
  G-      %   Subtract i, element-wise. This is the do...while loop condition (*).
}         % Finally (this is executed right before exiting the loop)
  @       %   Push current n. This is the output, to be displayed
          % End (implicit). A new iteration will start if all terms of (*) are nonzero
          % Display (implicit)
Luis Mendo
fuente
3

Adelante (gforth) , 106 bytes

: f
>r 0 begin 1+ dup begin dup i < while dup begin 10 /mod >r + r> ?dup 0= until repeat i = until rdrop
;

Pruébalo en línea!

Explicación del código

: f                \ start a new word definition
  >r               \ store the input on the return stack for easy access
  0                \ set up a counter
  begin            \ start an indefinite loop
    1+ dup         \ add 1 to the counter and duplicate
    begin          \ start a 2nd indefinite loop
      dup i <      \ check if current value is less than the input value
    while          \ if it is, continue with the inner loop
      dup          \ duplicate the current value
      begin        \ innermost loop, used to get the digit-wise sum of a number
        10 /mod    \ get quotient and remainder of dividing by 10
        >r + r>    \ add remainder to current list value
        ?dup 0=    \ check if quotient is 0
      until        \ end the innermost loop if it is
    repeat         \ go back to the beginning of the 2nd loop
    i =            \ check if the "last" value of the current list = the input value
  until            \ if it does, we're done
  rdrop            \ remove the input value from the return stack
;                  \ end the word definition    
reffu
fuente
3

Pyth , 13 bytes

fqQ.W<HQ+ssM`

Pruébalo aquí o echa un vistazo a la suite de prueba .


Cómo funciona

fqQ.W<HQ+ssM`     Full program. Takes input Q from STDIN, writes to STDOUT.
f{...}            Loop over 1,2,3,... and find the first number to yield truthy results when
                     applying the function {...} (whose variable is T = the current integer).
 qQ.W<HQ+ssM`     The function {...}, which will be analysed separately.
   .W             Functional while. While condition A is true, do B.
     <HQ          Cond. A (var: H - starts at T): Checks if H is less than Q.
        +ssM`     Func. B (var: G - G & H are the same): If A, G & H become G+digit sum(G)
                  The last value of this functional while will be the least possible number N
                  in the T-DSS that is greater than or equal to Q.
                  If N = Q, then Q ∈ T-DSS. Else (if N > Q), then Q ∉ T-DSS.
 q                That being said, check whether N == Q. 

nortek1nortenortenortek

Sr. Xcoder
fuente
1
Bien hecho, tenía fqQ.W<HQ+sjZ1014 años. ¡Siempre me olvido de 'y s como una forma de obtener dígitos de un número entero!
Sok
3

Jalea , 9 bytes

DS+)i$ƬṖṪ

Un enlace monádico que acepta un entero positivo nque produce un entero positivo a(n), el colombiano inverso de n.

Pruébalo en línea! O vea el conjunto de pruebas .

Cómo

Efectivamente, trabajamos hacia atrás, buscando repetidamente el valor que agregamos hasta que no podamos encontrar uno:

DS+)i$ƬṖṪ - Link: integer n
      Ƭ   - Repeat until a fixed point, collecting up:
     $    -   last two links as a monad - f(n):
   )      -     left links as a monad for each - [g(x) for x in [1..n]]:
D         -       decimal digits of x
 S        -       sum
  +       -       add x
    i     -     first (1-indexed) index of n in that list, or 0 if no found
       Ṗ  - pop of the rightmost value (the zero)
        Ṫ - tail

Usando 13como ejemplo ...

D  )  = [[1],[2],[3],[4],[5],[6],[7],[8],[9],[1,0],[1,1],[1,2],[1,3]]
 S    = [  1,  2,  3,  4,  5,  6,  7,  8,  9,    1,    2,    3,    4]
  +   = [  2,  4,  6,  8, 10, 12, 14, 16, 18,   11,   13,   15,   17]
    i 13 = .......................................... 11
    i 11 = .................................... 10
    i 10 = ............... 5
    i 5 = not found = 0 
    i 0 = not found = 0
    Ƭ -> [13, 11, 10, 5, 0]
    Ṗ =  [13, 11, 10, 5]
    Ṫ =               5
Jonathan Allan
fuente
2

Python 2 , 85 bytes

f=lambda n,a=[]:n in a and a.index(n)or f(n,[k+sum(map(int,`k`))for k in a]+[len(a)])

Pruébalo en línea!

Esto ciertamente funciona para todos los casos de prueba, más todas las entradas 1..88 dadas en OEIS; pero aún no estoy seguro de que sea demostrablemente correcto. (Esta es una de mis quejas con respecto a la Iglesia de la Unidad de Pruebas :)).

Chas Brown
fuente
re(X)Xdoyo(s)yosdoyo(0 0)=yo;doyo(s)=doyo(s-1)+Σre(doyo(s-1))X>1mire(X)(mi1)mire(X)(mi0 0)Σre(X)1
S(yo)doyo(S(yo))=norteΣre(doyo(s-1))1yo<yonorteS(yo),S(yo)S(yo)-S(yo)yo-yoyonorteyoa.index(n)
@Value Ink: Roger! Eso funciona totalmente. ¡Gracias!
Chas Brown
2

MathGolf , 13 bytes

╒môk(É∙Σ+=k/)

Pruébalo en línea!

¡Gran reto! Me hizo encontrar algunos errores dentro del comportamiento pop implícito de MathGolf, que agregó 1-2 bytes a la solución.

3

╒               range(1,n+1) ([1, 2, 3])
 mô             explicit map using 6 operators
   k(           push input-1 to TOS
     É          start block of length 3 (repeat input-1 times)
      ∙Σ+       triplicate TOS, take digit sum of top copy, and add that to second copy
                This transforms the array items to their respective sequences instead
                Array is now [1, 2, 4, 2, 4, 8, 3, 6, 12]
         =      get index of element in array (the index of 3 is 6)
          k/    divide by input (gives 2)
            )   increment (gives the correct answer 3)

Para demostrar que esto siempre funcionará, es fácil ver eso n <= input, porque inputes el primer elemento de la inputsecuencia th. Técnicamente, no he demostrado que esta solución sea siempre válida, pero supera todos los casos de prueba que he probado.

maxb
fuente
1

Limpio , 86 bytes

import StdEnv
$n=hd[i\\i<-[1..]|n==while((>)n)(\j=j+sum[toInt d-48\\d<-:toString j])i]

Pruébalo en línea!

Expandido:

$ n                    // function `$` of `n` is
 = hd [                // the first
   i                   // integer `i`
  \\                   // for
   i <- [1..]          // each integer from 1 upwards
  |                    // where 
   n ==                // `n` is equal to
   while ((>) n) (     // the highest value not more than `n` from
    \j = j + sum [     // `j` plus the sum of
      toInt d - 48     // the digital value
     \\                // for each
      d <-: toString j // digit in the string form of `j`
     ]                 // where `j` is the previous term
    )                  // of the sequence
   i                   // starting with term `i`
  ]

Me molesta que digitToInt dsea ​​más largo quetoInt d-48

Οurous
fuente
1

JavaScript, 65 bytes

n=>eval('for(i=p=1;n-p;p=p>n?++i:p)for(j=p;j;j=j/10|0)p+=j%10;i')

Pruébalo en línea!


También funciona como C, pero cuesta un byte más

C (gcc) , 66 bytes

i,p,j;f(n){for(i=p=1;n-p;p=p>n?++i:p)for(j=p;j;j/=10)p+=j%10;n=i;}

Pruébalo en línea!

tsh
fuente
1

Japt , 15 14 bytes

¡El ternario para manejar casos donde input=outputme molesta!

@Ç?X±ìx:XÃøU}a

Intentalo

@Ç?X±ìx:XÃøU}a     :Implicit input of integer U
@                  :A function taking an integer X as its argument
 Ç                 :  Map each Z in the range [0,U)
  ?                :    If Z>0
   X±              :      Increment X by
     ì             :      Convert X to digit array
      x            :      Reduce by addition
       :X          :    Else X
         Ã         :  End map
          øU       :  Contains U
            }      :End function
             a     :Return the first integer that returns true when passed through that function
Lanudo
fuente
1

cQuents , 18 bytes

#|1:#bN;A
=A?Z+UDZ

Pruébalo en línea!

Explicación

=A?Z+UDZ      second line - helper function
               first input = A
               second input = n
=A            first term is A
  ?           mode=query, return true if n in sequence, false if n not in sequence
              each term in the sequence equals
   Z+          previous term +
     U   )                     sum (                          )
      D )                            digits (               )
       Z                                      previous term

#|1:#bN;A     main program
               first input = A  (user input)
               second input = n
#|1           n = 1
   :          mode=sequence, return the nth term in the sequence
    #     )   conditional - next term equals next N that evaluates to true
              N increments, any terms that evaluate to true are added to the sequence
               conditional (                      )
     b   )                   second line (      )
      N;A                                  N, A
Stephen
fuente
1

Adelante (gforth) , 99 bytes

: f >r 0 begin 1+ dup begin dup i < while dup 20 for 10 /mod >r + r> next + repeat i = until r> . ;

Pruébalo en línea!

En gran medida similar a la presentación de reffu (106 bytes) . Las partes de golf son:

  • Cálculo de suma de dígitos (-6)
  • Limpieza final (-1) imprimiendo algo de basura en stdout. (No hay problema porque el resultado se devuelve en la parte superior de la pila).

Cómo funciona

: dsum ( n -- n+digitsum ) \ Sub-function. Given n, add its digit sum to n.
  dup                      \ Copy n to form ( n m ) -> extract digits from m and add to n
  20 for                   \ Repeat 20 times (a 64-bit int is at most 20 digits)
    10 /mod >r + r>        \   n += m%10, m = m/10
  next + ;                 \ End loop and discard 0

: f ( n -- ans )    \ Main function.
  >r                \ Move n to the return stack, so it can be referenced using `i`
  0 begin 1+        \ Initialize counter and loop starting from 1
    dup begin       \   Copy the counter (v) and loop
      dup i < while \     break if v >= n
      dsum          \     v += digit sum of v
    repeat          \   End loop
  i = until         \ End loop if n == v
  r> . ;            \ Cleanup the return stack so the function can return correctly
                    \ `r> .` is one byte shorter than `rdrop`
Bubbler
fuente
0

Carbón , 26 bytes

NθW¬№υθ«UMυ⁺κΣκ⊞υ⊕Lυ»I⊕⌕υθ

Pruébalo en línea! El enlace es a la versión detallada del código. Utiliza el algoritmo de @ ChasBrown. Si eso no es válido, entonces para 29 bytes:

NθW¬№υθ«≔⊕LυηW‹ηθ≧⁺Σηη⊞υη»ILυ

Pruébalo en línea! El enlace es a la versión detallada del código. Funciona calculando el primer miembro de cada secuencia de suma de dígitos como mínimo n. Explicación:

Nθ

Entrada n.

W¬№υθ«

Bucle hasta que nos encontramos con una secuencia de dígitos que contiene sumando n.

≔⊕Lυη

La siguiente secuencia comienza con una más que el número de secuencias hasta ahora.

W‹ηθ

Bucle mientras que el miembro de la secuencia es menor que n.

≧⁺Σηη

Agregue la suma de dígitos para obtener el siguiente miembro de la secuencia.

⊞υη

Empuje al miembro final a la lista.

»ILυ

Imprima el número de listas calculadas hasta que encontremos una que contenga n.

Neil
fuente
0

Rojo , 103 bytes

func[n][m: 1 loop n[k: m until[if k = n[return m]s: k
foreach d to""k[s: s + d - 48]n < k: s]m: m + 1]]

Pruébalo en línea!

Galen Ivanov
fuente
0

Gaia , 16 bytes

1⟨⟨:@<⟩⟨:Σ+⟩↺=⟩#

Pruébalo en línea!

Devuelve una lista que contiene el entero más pequeño.

1⟨	      ⟩#	% find the first 1 positive integers where the following is truthy:
	     =		% DSS equal to the input?
  	    ↺		% while
  ⟨:@<⟩			% is less than the input
       ⟨:Σ+⟩		% add the digital sum to the counter

Gaia , 16 bytes

1⟨w@⟨:):Σ++⟩ₓĖ⟩#

Pruébalo en línea!

Utiliza la observación hecha por el Sr. Xcoder . No es más corto que el otro, pero es un enfoque interesante.

1⟨	      ⟩#	% find the first 1 integers z where:
  	     Ė		% the input (n) is an element of
  w@⟨:):Σ++⟩ₓ		% the first n terms of the z-th Digital Sum Sequence

Gaia , 16 bytes

┅ẋ⟨@⟨:):Σ++⟩ₓĖ⟩∆

Pruébalo en línea!

Tercer enfoque que no utiliza N-find, #pero sigue confiando en la misma observación que el enfoque intermedio. Devuelve un entero en lugar de una lista.

Giuseppe
fuente
0

Clojure , 106 bytes

#(loop[j 1 i 1](if(= j %)i(if(< j %)(recur(apply + j(for[c(str j)](-(int c)48)))i)(recur(inc i)(inc i)))))

Pruébalo en línea!

Esto es 99 bytes, pero da como resultado un desbordamiento de pila en entradas más grandes (tal vez ajustar la JVM ayudaría):

#((fn f[j i](if(= j %)i(if(< j %)(f(apply + j(for[c(str j)](-(int c)48)))i)(f(inc i)(inc i)))))1 1)
NikoNyrh
fuente
0

Casco , 14 10 bytes

-4 gracias a @ H.PWiz

V£⁰m¡SF+dN

Pruébalo en línea!

Fruta Esolanging
fuente
Aquí hay 10 bytes: €mΩ≥¹SF+dN(sigo sintiendo que hay más corto)
H.PWiz
OV£⁰m¡SF+dN
H.PWiz
0

de tinta , 130 127 bytes

-(l)
+(i)[+]->l
*(w)[{i}]
~temp n=w
-(o){n<i:
~n+=s(n)
->o
}{n>i:->w}{w}
==function s(n)
{n>9:
~return n%10+s(n/10)
}
~return n

Pruébalo en línea!

  • -3 bytes convirtiendo a un programa completo que toma entrada unaria.

Esto se siente demasiado tiempo para no ser golfable.

Sin golf

// This program takes unary input. It passes through the same choice prompt as long as it recieves 1, and execution begins when it recieves 2
-(input_loop)
+(input_value)[+] -> input_loop                 // When this option (option 1) is selected, its read count is incremented. We can access this via the "input_value" variable. We then return to the prompt by going back to the "input_loop" gather
*(which_sequence)[{i}]                          // When this option (option 2) is selected, execution begins. Its read count also serves to keep track of which DSS we're checking.
~temp current_value = which_sequence            // The initial value for the n-DSS is n, of course.
-(sequence)                                     //
{current_value < input_value:                   // If we're still below the value we're looking for, we might find it.
    ~ current_value += digit_sum(current_value) // To get the next number, we add the current number's digit sum
    -> sequence                                 // Then we loop
}
{n > i: -> which_sequence}                      // If we get here, we're at or above our target number. If we're above it, we know it's the wrong sequence and move on to the next one by going back up to option 2. This increments its read count.
{which_sequence}                                // If we get here, we've found the target number, so we output the sequence's number.
// End of main stitch, program ends.

// A function to calculate the digit sum of a number
== function digit_sum(n) ==
{n > 9: // If given a number greater than 9, recurse
    ~ return (n % 10) + digit_sum(n / 10)
}
~ return n // Otherwise, return the input (it's a single digit)
Sara J
fuente