Знаменитая последовательность Фибоначчи F(0) = 0; F(1) = 1; F(N+1) = F(N) + F(N-1) (для этой задачи мы начинаем с 0).

Ваша задача: Дано п , выход сумма всех й - й чисел Фибоначчи для всех делителей d от п - го числа Фибоначчи. Если вы предпочитаете более формальную запись,

Входные данные : положительное целое число n

Выход : сумма

Например, рассмотрим n=4.F(4) = 3Делителями 3 являются 1 и 3, поэтому на выходе должно быть F(1) + F(3) = 1 + 2 = 3.

Для n=6, F(6) = 8и делители 8 равны 1, 2, 4, 8, поэтому на выходе F(1) + F(2) + F(4) + F(8) = 1 + 1 + 3 + 21 = 26.

Тестовые случаи:

1 => 1
2 => 1
3 => 2
4 => 3
5 => 6
6 => 26

Это код-гольф , самый короткий ответ в байтах выигрывает. Применяются стандартные лазейки .

На самом деле , 5 байтов

F÷♂FΣ

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

Как это устроено

       (implicit) Read n from STDIN.
F      Compute F(n).
 ÷     Get F(n)'s divisors.
  ♂F   Map F over the divisors.
    Σ  Take the sum.

Желе , 7 байт

ÆḞÆDÆḞS

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

Объяснение:

ÆḞÆDÆḞS Main link (Arguments: z)
ÆḞ      zth Fibonacci number's
  ÆD                           divisors'
    ÆḞ                                   Fibonacci numbers'
      S                                                     sum

Mathematica, 29 байт

f=Fibonacci;f@#~DivisorSum~f&

Mathematica упрощенный , 14 байтов

Fi@#~Div9`~Fi&

О, хорошо, это оказалось идентичным решению @ MartinEnder ...

Japt , 11 байт

MgU â x@MgX

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

05AB1E , 11 байт

!ÅFDI<èÑ<èO

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

объяснение

!            # factorial of input
 ÅF          # get the list of fibonacci numbers (starting at 1)
             # smaller than or equal to this
   D         # duplicate list of fibonacci number
    I<è      # get the element at index (input-1)
       Ñ     # get the list of its divisors
        <    # decrement each
         è   # get the fibonacci numbers at those indices
          O  # sum

Haskell, 54 байта

f=0:scanl(+)1f
g x=sum[f!!d|d<-[1..f!!x],mod(f!!x)d<1]

Пример использования: g 6-> 26. Попробуйте онлайн!

Алиса , 38 36 байт

Спасибо Лео за сохранение 2 байта.

/ow;B1dt&w;31J
\i@/01dt,t&w.2,+k;d&+

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

Почти наверняка не оптимально. Поток управления довольно сложный, и хотя я вполне доволен тем, сколько байтов было сохранено по сравнению с предыдущими версиями, у меня есть ощущение, что я слишком усложняю то, что может быть более простое и короткое решение.

объяснение

Во-первых, мне нужно немного разобраться со стеком обратных адресов Алисы (RAS). Как и во многих других фунгеоидах, у Алисы есть команда, позволяющая перемещаться по коду. Тем не менее, он также имеет команды, чтобы вернуться туда, откуда вы пришли, что позволяет довольно удобно реализовывать подпрограммы. Конечно, поскольку это двумерный язык, подпрограммы действительно существуют только по соглашению. Ничто не мешает вам войти в подпрограмму или выйти из нее с помощью других средств, кроме команды возврата (или в любой точке подпрограммы), и в зависимости от того, как вы используете RAS, в любом случае не может быть чистой иерархии перехода / возврата.

Как правило, это реализуется с помощью команды перехода, jпередающей текущий IP-адрес в RAS перед переходом. Команда return kзатем выводит адрес RAS и переходит туда. Если RAS пустой, kничего не делает вообще.

Есть и другие способы манипулирования РАН. Два из них имеют отношение к этой программе:

• wпроталкивает текущий IP-адрес в RAS, никуда не переходя. Если вы повторите эту команду, вы можете написать простые циклы довольно удобно, как &w...kя уже делал в предыдущих ответах.
• Jпохоже, jно не запоминает текущий IP-адрес на RAS.

Также важно отметить, что RAS не хранит информацию о направлении IP. Поэтому возвращение к адресу с kвсегда сохранит текущее направление IP (и, следовательно, также, находимся ли мы в режиме кардинала или ординала) независимо от того, как мы прошли через jилиw иной адрес IP-адреса.

Разобравшись с этим, давайте начнем с рассмотрения подпрограммы в приведенной выше программе:

01dt,t&w.2,+k

Эта подпрограмма вытягивает нижний элемент стека n наверх, а затем вычисляет числа Фибоначчи F (n) и F (n + 1) (оставляя их сверху стека). Нам никогда не нужен F (n + 1) , но он будет отброшен вне подпрограммы из-за того, как &w...kциклы взаимодействуют с RAS (какой тип требует, чтобы эти циклы были в конце подпрограммы). Причина, по которой мы берем элементы снизу, а не сверху, заключается в том, что это позволяет нам рассматривать стек больше как очередь, что означает, что мы можем вычислить все числа Фибоначчи за один раз, не сохраняя их в другом месте.

Вот как работает эта подпрограмма:

                                                          Stack
01    Push 0 and 1, to initialise Fibonacci sequence.     [n ... 0 1]
dt,   Pull bottom element n to top.                       [... 0 1 n]
t&w   Run this loop n times...                            [... F(i-2) F(i-1)]

  .     Duplicate F(i-1).                                 [... F(i-2) F(i-1) F(i-1)]
  2,    Pull up F(i-2).                                   [... F(i-1) F(i-1) F(i-2)]
  +     Add them together to get F(i).                    [... F(i-1) F(i)]

k     End of loop.

Конец цикла немного сложнее. Пока в стеке есть копия адреса 'w', начинается следующая итерация. Как только они исчерпаны, результат зависит от того, как была вызвана подпрограмма. Если подпрограмма была вызвана с помощью 'j', последняя «k» возвращается туда, так что конец цикла удваивается как возврат подпрограммы. Если подпрограмма была вызвана с помощью 'J', и в стеке все еще есть адрес с более раннего адреса, мы переходим туда. Это означает, что если подпрограмма была вызвана в самом внешнем цикле, это «k» возвращает в начало этого внешнего цикла. Если подпрограмма была вызвана с 'J', но RAS сейчас пуст, тогда это 'k' ничего не делает, и IP просто продолжает двигаться после цикла. Мы будем использовать все три этих случая в программе.

Наконец, к самой программе.

/o....
\i@...

Это всего лишь два быстрых перехода в обычный режим для чтения и печати десятичных целых чисел.

После i, есть a, wкоторый запоминает текущую позицию перед переходом в подпрограмму из-за второй /. Этот первый вызов подпрограммы вычисляет F(n)и F(n+1)на входе n. После этого мы возвращаемся назад, но сейчас движемся на восток, поэтому остальные операторы программы работают в режиме Cardinal. Основная программа выглядит так:

;B1dt&w;31J;d&+
        ^^^

Вот 31Jеще один вызов подпрограммы и, следовательно, вычисление числа Фибоначчи.

                                              Stack
                                              [F(n) F(n+1)]
;     Discard F(n+1).                         [F(n)]
B     Push all divisors of F(n).              [d_1 d_2 ... d_p]
1     Push 1. This value is arbitrary.        [d_1 d_2 ... d_p 1]
      The reason we need it is due to
      the fact that we don't want to run
      any code after our nested loops, so
      the upcoming outer loop over all
      divisors will *start* with ';' to
      discard F(d+1). But on the first
      iteration we haven't called the
      subroutine yet, so we need some 
      dummy value we can discard.
dt&w  Run this loop once for each element     [d_1 d_2 ... d_p 1]
      in the stack. Note that this is once    OR
      more than we have divisors. But since   [d_i d_(i+1) ... F(d_(i-1)) F(d_(i-1)+1)] 
      we're treating the stack as a queue,
      the last iteration will process the 
      first divisor for a second time. 
      Luckily, the first divisor is always 
      1 and F(1) = 1, so it doesn't matter 
      how often we process this one.

  ;     Discard the dummy value on the        [d_1 d_2 ... d_p]
        first iteration and F(d+1) of         OR
        the previous divisor on subsequent    [d_i d_(i+1) ... F(d_(i-1))]
        iterations.
  31J   Call the subroutine without pushing   [d_(i+1) ... F(d_i) F(d_i+1)]
        the current address on the RAS.
        Thereby, this doubles as our outer
        loop end. As long as there's an
        address left from the 'w', the end
        of the subroutine will jump there
        and start another iteration for the
        next divisor. Once that's done, the
        'k' at the end of the subroutine will
        simply do nothing and we'll continue
        after it.

;     Discard the final F(d_i+1).
d&+   Get the stack depth D and add the top   [final result]
      D+2 values. Of course that's two more
      than we have divisors, but the stack is
      implicitly padded with zeros, so that
      doesn't matter.

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

g==>fibonacci;f(x:NNI):NNI==(x<3=>1;reduce(+,map(g,divisors(g(x)))))

какой-то тест

(46) -> [[i,f(i)] for i in [0,1,2,3,4,5,6,10,15] ]
   (46)
   [[0,1], [1,1], [2,1], [3,2], [4,3], [5,6], [6,26], [10,139583862540],
     [15,
      135823697912782666169062844948067355657769395021071830756126284114988028_
       12823029319917411196081011510136735503204397274473084444
     ]
   ]
                                       Type: List List NonNegativeInteger

Пари / ГП , 34 байта

n->sumdiv((f=fibonacci)(n),x,f(x))

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

Python 2 , 89 84 байта

^{-5 байт благодаря овсу}

lambda n:sum(f(i)for i in range(1,f(n)+1)if f(n)%i<1)
f=lambda x:x<3or f(x-1)+f(x-2)

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

R 77 байт

F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)

Использует библиотеку 'gmp'. Это имеет встроенную функцию Фибоначчи и предоставляет возможность делать большие числа. Это вызвало несколько проблем с seqs и applys, хотя это все же меньше, чем создание моей собственной функции Фибоначчи.

объяснение

F=gmp::fibnum;               # Set F as fibnum function
N=F(scan());                 # get input and set N to the fibonacci number of that index
i=n=N-N;                     # set i and n to 0 with data type bigz
while(i<N)                   # loop while i < N
   if(N%%(i=i+1)<1)          # if incremented i is divisor of N 
       n=n+F(i);             # add F(i) to rolling sum
print(n)                     # output final result

Тестовое задание

> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 6
2: 
Read 1 item
Big Integer ('bigz') :
[1] 26
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 10
2: 
Read 1 item
Big Integer ('bigz') :
[1] 139583862540
> F=gmp::fibnum;N=F(scan());i=n=N-N;while(i<N)if(N%%(i=i+1)<1)n=n+F(i);print(n)
1: 15
2: 
Read 1 item
Big Integer ('bigz') :
[1] 13582369791278266616906284494806735565776939502107183075612628411498802812823029319917411196081011510136735503204397274473084444

Без использования gmp

81 байт , рекурсивная функция, которая безнадежно медленна, когда выбираются большие (9+) чисел

F=function(n)`if`(n<2,n,F(n-1)+F(n-2));sum(sapply(which((N=F(scan()))%%1:N<1),F))

88 байт , формула Бинета, которая будет работать достаточно хорошо с большими числами, но все же достигает целочисленного предела довольно быстро

F=function(n)round(((5+5^.5)/10)*((1+5^.5)/2)^(n-1));sum(F(which(F(N<-scan())%%1:N<1)))

Perl 6 , 49 байт

{my \f=0,1,*+*...*;sum f[grep f[$_]%%*,1..f[$_]]}

CJam , 26 байтов

qi_[XY@{_2$+}*]_@\f%:!.*:+

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

Я уверен, что это можно сделать лучше. Объяснение:

Идея состоит в том, чтобы иметь массив чисел Фибоначчи и расставить точки с массивом из 1 и 0, если это число является делителем ввода или не является его делителем.

qi                                 Read the input (n)
   [XY        ]                    Array starting with [1,2,...]
  _   @{_2$+}*                     Append n times the sum of the previous two
               _                   Duplicate the array
                @\f%               Modulo each item with n (0 if divisor, a number otherwise)
                    :!             Logical NOT everything (1 if divisor, 0 otherwise) 
                      .*:+         Dot product those two arrays

JavaScript (ES6), 76 65 байт

f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

Контрольные примеры

f=(n,i=k=(F=n=>n>1?F(n-1)+F(n-2):n)(n))=>i&&(k%i?0:F(i))+f(n,i-1)

console.log(f(1))
console.log(f(2))
console.log(f(3))
console.log(f(4))
console.log(f(5))
console.log(f(6))

JavaScript (ES6), 105 104 103 101 97 байт

i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s

Попытайся

f=
i=>[...Array((g=(n,x=0,y=1)=>n--?g(n,y,x+y):x)(i)+1)].map((_,y)=>s+=g((z=g(i)/y)%1?0:z|0),s=0)&&s
o.innerText=f(j.value=4)
oninput=_=>o.innerText=f(+j.value)

<input id=j type=number><pre id=o>

Q, 75 байт

{f:{$[x<2;x;.z.s[x-1]+.z.s[x-2]]};sum f each m where(~)b mod m:1+til b:f x}

C (gcc) , 93 90 80 байтов

F(n){n=n<2?n:F(n-1)+F(n-2);}i,s;f(n){for(s=0,i=F(n);i;i--)s+=F(n)%i?0:F(i);n=s;}

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

Добавить ++ , 89 байт

D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,r,@,¿1=,1,bM¿
D,g,@,¿1_,1_001${f},1¿{r}
D,d,@,{g}dF€gs

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