Fonction colombienne inverse

28

Définissons une séquence: la séquence de sommation à n chiffres (n-DSS) est une séquence qui commence par n . Si le dernier nombre était k , le nombre suivant est k + la somme des chiffres (k) . Voici les premiers 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...

Pour 1, c'est A004207 , bien que les premiers chiffres soient différents en raison d'une définition légèrement différente. Pour 3, c'est A016052 ; pour 9, A016096 .

Le défi d'aujourd'hui est de trouver la séquence de somme à n chiffres la plus basse dans laquelle un nombre donné apparaît. C'est ce qu'on appelle la "fonction colombienne inverse", et c'est A036233 . Les vingt premiers termes, commençant par 1 sont:

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

Quelques autres bons cas de test:

117: 9
1008: 918

Vous ne devez gérer que des entiers supérieurs à 0 et vous pouvez prendre des entrées et des sorties dans n'importe quel format standard. Comme d'habitude, c'est le golf de code , donc la réponse la plus courte dans chaque langue l'emporte.

code-golf sequence integer DJMcMayhem
la source

En relation

DJMcMayhem

Réponses:

12

Haskell , 104 64 63 octets

(-26 grâce à H.PWiz, -14 supplémentaire grâce au Sriotchilism O'Zaic, -1 supplémentaire grâce à cole)

Ceci est une fonction.

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

Essayez-le en ligne!

Explication:

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

Séquence de fonctions composées qui renvoie y + somme numérique de y. Convertit d'abord en chaîne, puis fait de la gymnastique monade pour obtenir la somme des caractères et le nombre d'origine (grâce à Cole).

L' <*>opérateur dans ce contexte a un type et une définition

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

afin que nous puissions écrire ce qui précède comme

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

Cela read . pureconvertit un Charen un nombre, (+) . read . pure :: Char -> Int -> Intajoute donc un chiffre à une valeur cumulée. Cette valeur est initialisée au nombre donné dans le pli.

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

untilapplique à plusieurs reprises une fonction à son résultat (dans ce cas, la somme numérique y + y) jusqu'à ce qu'elle réponde à une exigence spécifiée par une fonction dans le premier argument. Cela donne le plus petit élément y-DSS supérieur ou égal à x.

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

Liste paresseuse infinie de y telle que le plus petit élément y-DSS> = x est en fait x. Utilise la notation de compréhension de liste de Haskell (que j'avais aussi totalement oubliée, merci à tous).

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

Premier élément de cette liste, qui est le plus petit y qui satisfait l'exigence du défi.

Transformée de Fourier de Rin
la source

1

Voici comment je l'ai joué au golf.

H.PWiz

1

@ H.PWiz Cela devrait être le même non? Je pense que oui, mais votre utilisation fmapen premier lieu me déroute un peu.

Wheat Wizard

1

OK, il a fallu beaucoup de fenangling mais j'ai abusé de la monade de lecteur pour raser un seul octet. Woohoo code sans point! TIO

cole

@ SriotchilismO'Zaic Cool. Je viens de jouer au code mécaniquement, sans y penser

H.PWiz

1

Vous ne savez pas comment modifier la demande sur mobile, je viens de modifier une explication de mon code - n'hésitez pas à modifier ou à annuler.

cole

5

Python 2 , 73 71 octets

-2 octets grâce à Erik .

n=input();k=K=1
while n-k:K+=k>n;k=[k+sum(map(int,`k`)),K][k>n]
print K

Essayez-le en ligne!

ovs
la source

-2 en n'affectant pas làk>n .

Erik the Outgolfer

4

Perl 6 , 44 octets

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

Essayez-le en ligne!

Solution naïve qui vérifie chaque séquence jusqu'à ce qu'elle en trouve une contenant l'entrée

Explication:

->\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
la source

3

Rubis , 51 octets

->n{(1..n).find{|i|i+=i.digits.sum while i<n;i==n}}

Essayez-le en ligne!

Encre de valeur
la source

3

Gelée , 11 octets

D+ƒ$Ð¡€œi⁸Ḣ

Essayez-le en ligne!

Programme complet.

Erik le Outgolfer
la source

3

MATL , 18 octets

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

Essayez-le en ligne! Ou vérifiez les 20 premières valeurs .

Explication

Pour la saisie i, cela continue d'augmenter njusqu'à ce que les premiers itermes de la n-ième séquence soient inclus i. Il suffit de tester les itermes pour chaque séquence car la séquence augmente.

`         % 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
la source

3

Forth (gforth) , 106 octets

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

Essayez-le en ligne!

Explication du code

: 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
la source

3

Pyth , 13 octets

fqQ.W<HQ+ssM`

Essayez-le ici ou consultez la suite de tests .

Comment ça marche

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.

$n$ $k$ $1$ $n$ $n$ $n$ $k$

M. Xcoder
la source

1

Joliment fait, j'en ai eu fqQ.W<HQ+sjZ10pour 14. Je continue d'oublier `et s comme moyen d'obtenir des chiffres d'un entier!

Sok

3

Gelée , 9 octets

DS+)i$ƬṖṪ

Un lien monadique acceptant un entier positif nqui donne un entier positif a(n), le Colombien inverse de n.

Essayez-le en ligne! Ou consultez la suite de tests .

Comment

En fait, nous travaillons en arrière, en recherchant à plusieurs reprises la valeur à laquelle nous avons ajouté jusqu'à ce que nous n'en trouvions pas:

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

Utiliser 13comme exemple ...

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
la source

2

Python 2 , 85 octets

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)])

Essayez-le en ligne!

Cela fonctionne certainement pour tous les cas de test, ainsi que pour toutes les entrées 1 à 88 données à OEIS; mais je suis sûr que pas tout à fait c'est prouvable correct. (C'est l'une de mes plaintes concernant le Church Of Unit Testing :)).

Chas Brown
la source

d (x)

$d(x)$

x

$x$

C_{i} (s)

$C_i(s)$

i

$i$

s

$s$

C_{i} (0) = i; C_{i} (s) = C_{i} (s - 1) + Σ d (C_{i} (s - 1))

$C_i(0)=i; C_i(s)=C_i(s-1)+\Sigma d(C_i(s-1))$

x > 1

$x>1$

\exists e \in d (x) (e \geq 1)

$\exists e\in d(x) (e\geq1)$

\forall e \in d (x) (e \geq 0)

$\forall e\in d(x) (e\geq0)$

Σ d (x) \geq 1

$\Sigma d(x)\geq1$

S (i)

$S(i)$

C_{i} (S (i)) = n

$C_i(S(i))=n$

Σ d (C_{i} (s - 1)) \geq 1

$\Sigma d(C_i(s-1))\geq1$

i < i^{'} \leq n

$i<i'\leq n$

S (i), S (i^{'})

$S(i),S(i')$

S (i^{'}) - S (i) \leq i^{'} - i

$S(i')-S(i)\leq i'-i$

i

$i$

n

$n$

i

$i$ a.index(n)

@Value Ink: Roger! Cela fonctionne totalement. Merci!

Chas Brown

2

Wolfram Language (Mathematica) , 61 octets

For[j=i,#>=j,j=j+Tr@IntegerDigits@j,j/.#->Return@i]~Do~{i,#}&

Essayez-le en ligne!

attinat
la source

2

MathGolf , 13 octets

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

Essayez-le en ligne!

Grand défi! Cela m'a amené à trouver quelques bugs dans le comportement pop implicite de MathGolf, qui a ajouté 1-2 octets à la solution.

$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)

Pour prouver que cela fonctionnera toujours, il est facile de voir cela n <= input, car inputc'est le premier élément de la inpute séquence. Je n'ai techniquement pas prouvé que cette solution est toujours valide, mais elle réussit tous les cas de test que j'ai testés.

maxb
la source

2

05AB1E , 13 octets

L.ΔIGÐSO+})Iå

Essayez-le en ligne!

Grimmy
la source

1

Nettoyer , 86 octets

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

Essayez-le en ligne!

Étendu:

$ 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`
  ]

Ça me dérange c'est digitToInt dplus quetoInt d-48

Οurous
la source

1

C (gcc) , 102 octets

f(n,i,s){for(i=1;n^s;)for(s=i++;s<n;){char*p,j=0,l=asprintf(&p,"%d",s);for(;j<l;)s+=p[j++]-48;}n=~-i;}

Essayez-le en ligne!

Οurous
la source

1

JavaScript, 65 octets

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')

Essayez-le en ligne!

Il fonctionne également en C, mais coûte un octet de plus

C (gcc) , 66 octets

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;}

Essayez-le en ligne!

tsh
la source

1

C # (Visual C # Interactive Compiler) , 83 , 82 octets

n=>Enumerable.Range(1,n).First(x=>{for(;x<n;x+=(x+"").Sum(c=>c-48));return x==n;})

Essayez-le en ligne!

Innat3
la source

1

82 octets

Données expirées

@ExpiredData ah oui comment ai-je oublié d'utiliser la valeur littérale x)

Innat3

1

Japt , 15 14 octets

Le ternaire pour gérer les cas où input=outputça m'ennuie!

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

@Ç?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

Hirsute
la source

1

cQuents , 18 octets

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

Essayez-le en ligne!

Explication

=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
la source

1

Forth (gforth) , 99 octets

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

Essayez-le en ligne!

Largement similaire à la soumission de reffu (106 octets) . Les parties golfées sont:

Calcul de la somme des chiffres (-6)
Nettoyage final (-1) en imprimant des ordures sur stdout. (Pas de problème car le résultat est renvoyé en haut de la pile.)

Comment ça marche

: 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
la source

0

Fusain , 26 octets

ＮθＷ¬№υθ«ＵＭυ⁺κΣκ⊞υ⊕Ｌυ»Ｉ⊕⌕υθ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Utilise l'algorithme de @ ChasBrown. Si cela s'avère invalide, alors pour 29 octets:

ＮθＷ¬№υθ«≔⊕ＬυηＷ‹ηθ≧⁺Σηη⊞υη»ＩＬυ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Fonctionne en calculant le premier membre de chaque séquence de sommation de chiffres au moins n. Explication:

Ｎθ

Entrée n.

Ｗ¬№υθ«

Boucle jusqu'à ce que nous trouvions une séquence de sommation de chiffres contenant n.

≔⊕Ｌυη

La séquence suivante commence avec une de plus que le nombre de séquences jusqu'à présent.

Ｗ‹ηθ

Boucle pendant que le membre de la séquence est inférieur à n.

≧⁺Σηη

Ajoutez la somme des chiffres pour obtenir le prochain membre de la séquence.

⊞υη

Poussez le dernier membre dans la liste.

»ＩＬυ

Imprimez le nombre de listes calculées jusqu'à ce que nous en trouvions une contenant n.

Neil
la source

0

Rouge , 103 octets

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]]

Essayez-le en ligne!

Galen Ivanov
la source

0

CJam , 25 octets

q~:T,{[){__Ab:++}T*]T&}#)

Essayez-le en ligne!

Esolanging Fruit
la source

0

Gaia , 16 octets

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

Essayez-le en ligne!

Renvoie une liste contenant le plus petit entier.

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 octets

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

Essayez-le en ligne!

Utilise l'observation faite par M. Xcoder . Ce n'est pas plus court que l'autre, mais c'est quand même une approche intéressante.

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 octets

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

Essayez-le en ligne!

Troisième approche ne pas utiliser N-find, #mais toujours compter sur la même observation que l'approche du milieu. Renvoie un entier plutôt qu'une liste.

Giuseppe
la source

0

Clojure , 106 octets

#(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)))))

Essayez-le en ligne!

Il s'agit de 99 octets mais entraîne un dépassement de capacité de la pile sur des entrées plus importantes (peut-être que l'ajustement de la JVM pourrait aider):

#((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
la source

0

C # (Visual C # Interactive Compiler) , 75 octets

n=>{int a=0,b=0;for(;b!=n;)for(b=++a;b<n;)b+=(b+"").Sum(x=>x-48);return a;}

Essayez-le en ligne!

Incarnation de l'ignorance
la source

0

Husk , 14 10 octets

^{-4 merci à @ H.PWiz}

V£⁰m¡SF+dN

Essayez-le en ligne!

Esolanging Fruit
la source

Voici 10 octets: €mΩ≥¹SF+dN(je sens toujours qu'il y a plus court)

H.PWiz

OuV£⁰m¡SF+dN

H.PWiz

0

encre , 130 127 octets

-(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

Essayez-le en ligne!

-3 bytes en convertissant en un programme complet qui prend une entrée unaire.

Cela semble trop long pour ne pas être jouable au golf.

Non 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
la source

0

C (gcc) , 80 79 78 octets

i,j;r;v;f(n){for(r=v=n;i=--r;v=n-i?v:r)for(;i<n;)for(j=i;i+=j%10,j/=10;);n=v;}

Essayez-le en ligne!

-2 au plafond

attinat
la source