Факториалы и бесконечные циклы!

33

Как вы, возможно, знаете, факториал натурального числа nявляется произведением всех натуральных чисел, равных или меньших n.

Например :

6! = 6*5*4*3*2*1 = 720
0! = 1

Теперь мы определим специальную операцию с нерелевантным именем, например sumFac:

Учитывая положительное целое число n, sumFac(n)это сумма факториалов цифр.

Например :

sumFac(132) = 1! + 3! + 2! = 9

задача

Ваша миссия, независимо от того, решите вы ее принять или нет, состоит в том, чтобы вернуть последовательность (потенциально бесконечную) применений sumFacцелого числа, указанного во входных данных.

Пример : 132 -> 132, 9, 362880, 81369, 403927, ...

Но это не все! Действительно, приложения в sumFacконечном итоге создадут цикл. Вы также должны вернуть этот цикл!

Если ваш язык имеет встроенный факториал, вы можете использовать его. Я не придирчив к типу возвращаемого значения, вам просто нужно вернуть последовательность приложений sumFac и цикл в формате, понятном человеку.

РЕДАКТИРОВАТЬ: Чтобы помочь вам лучше визуализировать, как должен выглядеть вывод, я скопировал Leaky Nun чуть ниже:

[132, 9, 362880, 81369, 403927, 367953, 368772, 51128, 40444, 97, 367920, 368649, 404670, 5810, 40442, 75, 5160, 842, 40346, 775, 10200, 6, 720, 5043, 151, 122, 5, 120, 4, 24, 26, 722, 5044, 169, 363601, 1454]

Вам просто нужно остановить последовательность, когда цикл собирается начать во второй раз!

Но это код-гольф, поэтому выигрывает самый короткий ответ в байтах!

Leaderboard

Вот фрагмент стека, который генерирует как регулярную таблицу лидеров, так и обзор победителей по языкам.

Дрянная Монахиня
источник
Related
Leaky Nun
Добро пожаловать в PPCG! Кстати, это хороший вызов.
clismique
@ Qwerp-Derp Спасибо большое! Я пытался быть креативным ^^
@Zgarb Ну, это как выход Leaky Nun. Последовательность заявлений, а затем она заканчивается до начала второго цикла. Я скопирую его вывод в вопросе, чтобы каждый мог иметь четкое понимание. Спасибо за указание на это :)
1
@ 2501 Жесткое кодирование значения обманывает, но в отношении выходного форматирования вы можете использовать любой разделитель, который вам нужен

Ответы:

19

Желе , 6 байт

D!SµÐĿ
    ÐĿ  Repeat until the results are no longer unique. Collects all intermediate results.
D           Convert from integer to decimal (list of digits)
 !          Factorial (each digit)
  S         Sum

Попробуйте онлайн!

Я не вижу другого способа сделать его короче, кроме как делать, как сказано.

Спекуляции

  • Входные данные: 132 (как аргумент командной строки)
  • Выход: [132, 9, 362880, 81369, 403927, 367953, 368772, 51128, 40444, 97, 367920, 368649, 404670, 5810, 40442, 75, 5160, 842, 40346, 775, 10200, 6, 720, 5043, 151, 122, 5, 120, 4, 24, 26, 722, 5044, 169, 363601, 1454]
Дрянная Монахиня
источник
Я не ожидал получить такой короткий ответ. Ницца :)
4
@Antoine Это желе: D Это всегда короче, чем я думаю;)
HyperNeutrino
8
@HyperNeutrino Каким-то образом Деннис придет с еще более коротким ответом
Leaky Nun
Почему-то да. Потому что Деннис. : P
HyperNeutrino
Итак ... Какую кодировку символов вы используете, чтобы получить 6 байтов для этих 6 символов? Разве Jelly не должен быть в кодировке UTF-8, означая, что эта программа на самом деле имеет 9 байтов?
LordOfThePigs
9

05AB1E , 12 байтов

[DˆS!O©¯så#®

Попробуйте онлайн!

объяснение

[               # infinite loop
 Dˆ             # add a copy of current value to the global list (initialized as input)
   S            # split current number to digits
    !O          # calculate factorial of each and sum
      ©         # save a copy in register
       ¯så#     # if the current number is in the global list, exit loop
           ®    # retrieve the value from the register for the next iteration
                # implicitly output the global list
Emigna
источник
Коротко и правильно, хорошо сыграно!
Думал, что смогу избавиться от этого s, был неправильный, хороший ответ.
Волшебная урна осьминога
8

Брахилог , 17 байт

g:I{tẹḟᵐ+}ᵃ⁾L¬≠Lk

Попробуйте онлайн!

объяснение

g:I{     }ᵃ⁾         Accumulate I (a variable) times, with [Input] as initial input:
    t                  Take the last integer
     ẹḟᵐ+              Compute the sum of the factorial of its digits
            L        The result of the accumulation is L
            L­      Not all elements of L are different
               Lk    Output is L minus the last one (which is the start of the loop)
Fatalize
источник
Что Iзначит?
Утренняя монахиня
1
@LeakyNun Это параметр для ᵃ⁾. ᵃ³означает «накапливать 3 раза». ᵃ⁾означает «накапливать столько раз, сколько последний элемент ввода», что в этом случае I. Так Iкак это полностью свободная переменная, она будет пытаться значения для нее от 0до +inf.
Роковая
8

Wolfram Language, 62 60 56 байт

Most@NestWhileList[Tr[IntegerDigits@#!]&,#,UnsameQ,All]&

Очень плохо, что в Wolfram Language есть такие отвратительно длинные имена функций. *Вздох*

Объяснение:

Most[NestWhileList[Tr[IntegerDigits[#]!]&,#,UnsameQ,All]]&
                      IntegerDigits[#]                     (*Split input into list of digits*)
                                      !                    (*Factorial each element in the list*)
                   Tr[                 ]&                  (*Sum the list together*)
     NestWhileList[                      ,#,UnsameQ,All]   (*Iterate the function over itself, pushing each to a list, until a repeat is detected*)
Most[                                                   ]& (*Remove the last element in the list*)
Скотт Милнер
источник
Хороший ответ. Я не думаю, что это можно улучшить.
Келли Лоудер
1
@KellyLowder Спасибо! На самом деле я смог сохранить еще два байта, сопоставив факториал со списком, а затем суммировав его Tr.
Скотт Милнер
1
Хорошее использование NestWhileList[...,All]!
Грег Мартин,
6

JavaScript (ES6), 91 89 байт

Сохранено 2 байта благодаря fəˈnɛtɪk

Оказывается, он очень похож на другой ответ JS .

f=(n,x=!(a=[n]))=>n?f(n/10|0,x+(F=n=>n?n--*F(n):1)(n%10)):~a.indexOf(x)?a:f(x,!a.push(x))

Arnauld
источник
В вашей факториальной функции вы не можете использовать n вместо n> 1, потому что 0! = 1?
fəˈnɛtɪk
@ fəˈnɛtɪk Я не знаю, о чем я тут думал. Спасибо!
Arnauld
5

ClojureScript, 146 109 байт

#(loop[n[%]](let[f(apply +(for[a(str(last n))](apply *(range 1(int a))))](if(some #{f}n)n(recur(conj n f)))))

Да, это чудовище. Кто-нибудь, пожалуйста, помогите мне в этом ...

Спасибо, @cliffrootчто сбрил колоссальные 37 байт!

Это анонимная функция, для запуска функции необходимо сделать следующее:

(#(...) {arguments})

TIO не имеет ClojureScript, поэтому вот ссылка на REPL ClojureScript.

Вот ссылка на программу Clojure, которая печатает последний элемент в списке от 0 до 1000.

Вот вывод для 9999:

[9999 1451520 269 363602 1455 265 842 40346 775 10200 6 720 5043 151 122 5 120 4 24 26 722 5044 169 363601 1454]

У меня есть сильное подозрение, что все числа должны в конечном итоге обосноваться на 1 или петле [169 363601 1454].

Ungolfed код:

(defn fact-cycle [n]
  (loop [nums [n]]
    (let [fact-num
          (let [str-n (str (last nums))]
            (apply +
              (for [a (range (count str-n))]
                (apply *
                  (range 1
                    (inc (int (nth str-n a))))))))]
      (if (some #{fact-num} nums) nums
        (recur
          (conj nums fact-num))))))

Объяснение скоро!

clismique
источник
Довольно долго, но правильно;) Я не могу помочь тебе в этом гольфе извините ^^
внутреннее forможет быть (for[a s](apply *(range 1(-(int a)47)))), не так ли?
Утес
и это позволит избавиться от другогоlet #(loop[n[%]](let[f(apply +(for[a(str(last n))](apply *(range 1(-(int a)47)))))](if(some #{f}n)n(recur(conj n f)))))
обломок
о, кажется, вам даже не нужен (- ... 47)ClojureScript, просто intбудет достаточно
cliffroot
ну, (inc(int a))следует сделать для ClojureScript и (-(int a)47)для Clojure.
Утес
5

Perl 6 , 64 байта

{my@a;$_,{[+] .comb.map:{[*] 2..$_}}...^{$_@a||!@a.push: $_}}

Попытайся

Expanded:

{

  my @a;             # array of values already seen

  $_,                # seed sequence with the input

  {
    [+]              # reduce using &infix:<+>
      .comb          # the digits of $_ (implicit method call)
      .map:          # do the following for each
      {
        [*] 2..$_    # get the factorial of
      }
  }


  ...^               # keep generating values until
                     # (「^」 means throw away the last value when done)

  {
      $_  @a        # is it an elem of @a? (「∈」 is shorter than 「(cont)」)

    ||               # if it's not

      !              # boolean invert so this returns False
        @a.push: $_  # add the tested value to @a
  }
}

Каждая строка выше этого имеет {новый лямбда-блок с неявным параметром $_.

Я использовал [*] 2..$_вместо [*] 1..$_чисто микро оптимизации.

Брэд Гилберт b2gills
источник
4

JavaScript, 92 байта

Спасибо @Shaggy за игру в один байт с включенными
включением Спасибо @Neil за игру в гольф с двумя байтами

Код разделен на отдельные функции 92 байта

f=(x,a=[])=>a.includes(x)?a:f(k(x),a,a.push(x))
p=y=>y?y*p(y-1):1
k=n=>n?p(n%10)+k(n/10|0):0

Код в одной строке 92 байта

f=(x,a=[])=>a.includes(x)?a:f((k=n=>n?(p=y=>y?y*p(y-1):1)(n%10)+k(n/10|0):0)(x),a,a.push(x))

объяснение

Сначала вызовите функцию только с одним аргументом, поэтому a = [].

Если x существует в массиве, возвращается a.includes(x)?a:...

В противном случае добавьте x к a и передайте сумму цифр факториала и a в функцию (a.push(x),f(k(x),a))

p=y=>y?y*p(y-1):1
k=n=>n?p(n%10)+k(n/10|0):0

Сумма Factorial Digit выполнена так, чтобы она не превышала максимального предела рекурсии.

Список всех возможных конечных точек: 1, 2, 145, 169, 871, 872, 1454, 40585, 45361, 45362, 363601

Попробуйте онлайн!

fənɛtɪk
источник
1
Гах, я был так близко! Сохранить байт сf=(x,a=[])=>a.includes(x)?a:(a.push(x),f(k(x),a))
Shaggy
Вы не можете написать f(k(x),a,a.push(x))? Кроме того, я думаю, что вы можете написать, k=n=>n&&чтобы сохранить еще один байт.
Нил
4

Haskell , 80 67 байт

g#n|elem n g=g|h<-g++[n]=h#sum[product[1..read[d]]|d<-show n]
([]#)

Попробуйте онлайн!Использование:([]#) 132

Изменить: 13 байтов с типами от Орджана Йохансена!

Laikoni
источник
(1) Тестируйте и добавляйте nвместо s(так же, как в ответе Python от ovs), затем f=([]#). (2) Переключите ветви, встроенные sи используйте elem.
Орджан Йохансен
Переключите ваш ++FOR :также.
1
@ Каньон Это неправильный порядок для этого, это дало бы обратный конечный результат. Вы можете почти все исправить, предварительно добавив лишнее n:и изменив =gна =[], но, похоже, это всего лишь ничья.
Орджан Йохансен,
4

Pyth, 9 байт

.us.!MjNT
.us.!MjNTQ  implicit Q

.u          explained below
       N      current value
      j T     convert to decimal (list of digits)
   .!M        factorial of each digit
  s           sum

Попробуйте онлайн!

Этот ответ использует .u(«Накопительная фиксированная точка. Применять до тех пор, пока не будет найден результат, полученный до того, как будет найден. Вернуть все промежуточные результаты».)

Дрянная Монахиня
источник
3

Pyth, 30 байт

W!hxYQQ=+YQKQ=Q0WK=+Q.!%KT=/KT

Попробуй здесь

Мария
источник
Pyth имеет больше полезных функций, чем можно себе представить. Смотрите мой ответ как ссылку.
Утренняя монахиня
2

R, 120 байт

o=scan()
repeat {
q=sum(factorial(as.double(el(strsplit(as.character(o[length(o)]), "")))))
if(q%in%o)break
o=c(o,q)
}
o
Нил
источник
Вы можете сделать o=scan(), использовать el()вместо [[1]], и, как gamma(n+1)=factorial(n)я считаю, сохраняет байт, и я думаю, что as.numericто же самое, что и as.doubleдля целых чисел, которые также сохраняют байт, и вы можете использовать toStringвместо as.character.
Джузеппе
@Giuseppe Спасибо за вклад, обновлено.
Нил
2

Java 9 JSHell, 213 байт

n->{Set<Integer>s=new HashSet<>();
return IntStream.iterate(n,i->(""+i).chars()
.map(x->x<50?1:IntStream.rangeClosed(2,x-48)
.reduce(1,(a,b)->a*b)).sum()).boxed()
.takeWhile(x->s.add(x)).collect(Collectors.toList());}

Попробуйте онлайн!

Примечание. Это решение основано на строковом представлении числа, имеющего кодовые точки в диапазоне 48-57. Работает для ASCII, UTF-8, Latin-1, всех наборов символов ISO-8859- *, большинства кодовых страниц. Не работает для EBCDIC. Я не думаю, что кто-то вычитает очки за это. :)

Ungolfed:

Function<Integer, List<Integer>> f =        // function from Integer to List of Integer
n -> {
    Set<Integer> s = new HashSet<>();       // memo of values we've seen
    return IntStream.iterate(n,             // iterate over n, f(n), f(f(n)), etc.
    i -> (""+i).chars()                     // the sumFac function; for all chars
        .map(x -> x < 50? 1 :               // give 1 for 0! or 1!
        IntStream.rangeClosed(2, x-48)      // else produce range 2..d 
        .reduce(1,(a,b)->a*b))              // reduction to get the factorial
        .sum())                             // and sum up the factorii!

                                            // now we have a stream of ints
                                            // from applying sumFac repeatedly
        .boxed()                            // box them into Integers (thanks, Java)
        .takeWhile(x->s.add(x))             // and take them while not in the memo
        .collect(Collectors.toList());      // collect them into a list
}

Заметки:

  • Возвращаемое значение Set :: add очень полезно здесь; возвращает истину, если элемент не был в наборе
  • Я был саркастичен, когда сказал "Спасибо, Ява"
  • на самом деле фактория - это не слово; Я только что сделал это
Дэвид Конрад
источник
1
Я признаю, что это оригинально! Отличная работа :)
@ Антуан Признаюсь, Ява не лучший язык для игры в гольф, но вряд ли это была самая сумасшедшая вещь, которую я сделал за последнее время. :) codegolf.stackexchange.com/a/117644/794
Дэвид Конрад
2

Pyth, 22 11 bytes

.usm.!sd+Nk

Try it online!

Lots of credit to Leaky Nun's answer, which introduced me to .u, and helped save a massive 11 bytes of this program.

Explanation:

.usm.!sd+NkQ | ending Q is implicitly added
             | Implicit: Q = eval(input())
.u         Q | Repeat the function with initial value Q until a previous value is found. Return all intermediate values
  s          | Summation
   m.!sd     | For each character 'd' in the string, convert to integer and take the factorial
        +Nk  | Convert function argument to string
K Zhang
источник
Pyth имеет больше полезных функций, чем можно себе представить. Смотри мой ответ as reference.
Leaky Nun
@ LeakyNun Я переписал свой ответ, чтобы использовать .u. Думаю, мне нужно еще раз просмотреть ссылку на символ, чтобы увидеть, есть ли там другие полезные функции.
К Чжан
Вы можете использовать `Nдля преобразования в строку вместо +Nk.
Утренняя монахиня
@LeakyNun Где то Nустареет тогда, и приходит 9-байтовое решение ...
Эрик Outgolfer
1

Аксиома, 231 байт

l(a:NNI):List NNI==(r:List NNI:=[];repeat(r:=cons(a rem 10,r);a:=a quo 10;a=0=>break);r)
g(a:NNI):NNI==reduce(+,[factorial(x) for x in l(a)])
h(a:NNI):List NNI==(r:=[a];repeat(a:=g(a);member?(a,r)=>break;r:=cons(a,r));reverse(r))

не гольфовые функции и некоторый тест

-- convert one NNI in its list of digits
listify(a:NNI):List NNI==
    r:List NNI:=[]
    repeat
        r:=cons(a rem 10,r)
        a:=     a quo 10
        a=0=>break
    r

-- g(1234)=1!+2!+3!+4!
SumfactorialDigits(a:NNI):NNI==reduce(+,[factorial(x) for x in listify(a)])

ListGenerateFromSumFactorialDigits(a:NNI):List NNI==
    r:=[a]
    repeat
       a:=SumfactorialDigits(a)
       member?(a,r)=>break
       r:=cons(a,r)
    reverse(r)

(9) -> h 132
   (9)
   [132, 9, 362880, 81369, 403927, 367953, 368772, 51128, 40444, 97, 367920,
    368649, 404670, 5810, 40442, 75, 5160, 842, 40346, 775, 10200, 6, 720,
    5043, 151, 122, 5, 120, 4, 24, 26, 722, 5044, 169, 363601, 1454]
RosLuP
источник
1

Java 7, 220 байт

String c(int n){String r=n+",",c;for(;!r.matches("^"+(c=(n=d(n))+",")+".*|.*,"+c+".*");r+=c);return r;}int d(int n){int s=0;for(String i:(n+"").split(""))s+=f(new Long(i));return s;}long f(long x){return x<2?1:x*f(x-1);}

Объяснение:

String c(int n){                            // Method with integer parameter and String return-type
  String r=n+",",                           //  Result-String (which starts with the input integer + a comma
         c;                                 //  Temp String
  for(;!r.matches(                          //  Loop as long as the result-String doesn't match the following regex:
    "^"+(c=(n=d(n))+",")+".*|.*,"+c+".*");  //    "^i,.*|.*,i,.*" where `i` is the current integer
                                            //   `n=d(n)` calculates the next integer in line
                                            //   `c=(n=d(n))+","` sets the temp String to this integer + a comma
    r+=c                                    //   And append the result-String with this temp String
  );                                        //  End of loop
  return r;                                 //  Return the result-String
}                                           // End of method

int d(int n){                               // Separate method (1) with integer parameter and integer return-type
  int s=0;                                  //  Sum
  for(String i:(n+"").split(""))            //  Loop over the digits of `n`
    s+=f(new Long(i));                      //   And add the factorial of these digits to the sum
                                            //  End of loop (implicit / single-line body)
  return s;                                 //  Return the sum
}                                           // End of separate method (1)

long f(long x){                             // Separate method (2) with long parameter and long return-type (calculates the factorial)
                                            // (NOTE: 2x `long` and the `new Long(i)` is shorter than 2x `int` and `new Integer(i)`, hence long instead of int)
  return x<2?                               //  If `x` is 1:
      1                                     //   return 1
    :                                       //  Else:
      x*f(x-1);                             //   return `x` multiplied by the recursive-call of `x-1`
}                                           // End of method (2)

Тестовый код:

Попробуй это здесь.

class M{
  String c(int n){String r=n+",",c;for(;!r.matches("^"+(c=(n=d(n))+",")+".*|.*,"+c+".*");r+=c);return r;}int d(int n){int s=0;for(String i:(n+"").split(""))s+=f(new Long(i));return s;}long f(long x){return x<2?1:x*f(x-1);}

  public static void main(String[] a){
    System.out.println(new M().c(132));
  }
}

Выход:

132,9,362880,81369,403927,367953,368772,51128,40444,97,367920,368649,404670,5810,40442,75,5160,842,40346,775,10200,6,720,5043,151,122,5,120,4,24,26,722,5044,169,363601,1454,
Кевин Круйссен
источник
1

GolfScript , 44 байта

~]{..)\;10base{,1\{)*}/}%{+}*.@\+@@?)!}do);`

~                                             eval input
 ]                                            initialization
  {                                   }do     do...
   ..)\;                                          initialization
        10base                                    get digits
              {,1\{)*}/}%                         factorial each
                         {+}*                     sum
                             .@\+@@?)!        while result not found
                                         );   drop last element
                                           `  tostring

Попробуйте онлайн!

Факторная часть отсюда .

Дрянная Монахиня
источник
1

TI-BASIC, 85 79 64 60 байт

:Prompt L₁                             //Get input as 1 length list, 4 bytes
:Lbl C                                //create marker for looping, see below, 3 bytes
:int(10fPart(Xseq(10^(~A-1),A,0,log(X //split input into list of digits, 20 bytes
:sum(Ans!→X                           //factorial and sum the list, write to new input, 6 bytes
:If prod(L₁-X                         //Test to see if new element is repeated, see below, 7 bytes
:Then                                 //Part of If statement, 2 bytes
:augment(L₁,{X→L₁                     //Push new input to List 1, 10 bytes
:Goto C                               //Loop back to beginning, 3 bytes
:Else                                 //Part of If statement, 2 bytes
:L₁                                   //Print Answer, 2 bytes

Поскольку он работает на графическом калькуляторе, объем ОЗУ ограничен. Попробуйте проверить это с числами, которые зацикливаются быстро, как 169.

Более объяснение:

:int(10fPart(Xseq(10^(~A-1),A,0,log(X
              seq(10^(~A-1),A,0,log(X //Get a list of powers of 10 for each digit (i.e. 1, 0.1, 0.01, etc.)
             X                        //Multiply by input
       fPart(                         //Remove everything but the decimal
     10                               //Multiply by 10 (move one digit in front of the decimal
:int(                                 //Truncate to an integer

If prod(L₁-Xработает, вычитая новый элемент из старого списка, затем умножая все элементы списка вместе. Если элемент уже был в списке, продукт будет 0ошибочным значением. В противном случае произведение будет целым положительным, истинным значением.

Скотт Милнер
источник
1

J , 40 31 байт

Редактировать: 9 байтов сохранены с использованием улучшений FrownyFrog. Благодарность!

f=.$:@,~`]@.e.~[:+/@:!10#.inv{:

Оригинальный код:

е = [ `($: @,) @.. ([: - е. ~.) [: + / @ (0 & ": @ {:)!»."

В этом случае я решил подсчитать байты для определения глагола, так как в противном случае он не работает в интерпретаторе.

Объяснение:

                         ({:) - принимает последний элемент массива
                               ": @ - преобразовывает его в строку
                          "." 0 & - преобразует каждый символ обратно в целое число
                       ! @ - находит факториалы
                     + / - суммирует их
                   [: - cap (есть 2 производных глагола выше, нам нужно 3 для вилки)
          (e. ~) - проверить, присутствует ли результат в списке    
             -. - отменяет вышеуказанную проверку
           [: - крышка
        @. - Повестка дня соединения, необходимая для рекурсии
  ($: @,) - если результата нет в списке, добавьте его в список и повторите
[`                                    - if the result is in the list, display it and stop    

Try it online!

Galen Ivanov
источник
1
([:-.e.~) -> (1-e.~)
FrownyFrog
1
31 bytes
FrownyFrog
@FrownyFrog Thanks, your code is much better! I tried 10#.inv early while experimenting, but then I wrote it 10&#.inv and it was longer, so I rejected it. Thanks for all your suggestions! I have much to learn :)
Galen Ivanov
@FrownyFrog Reversing the cases for the agenda is so good, I regret I didn't see it :)
Galen Ivanov
[:+/!@"."0@":@{: is the same length, so there's no improvement with 10#.inv. Just had to drop the ().
FrownyFrog
1

Tcl, 143 bytes

proc P {n L\ ""} {proc F n {expr $n?($n)*\[F $n-1]:1}
while {[set n [expr [join [lmap d [split $n ""] {F $d}] +]]] ni $L} {lappend L $n}
set L}

Try it online!

sergiol
источник