Сумма моих делителей Фибоначчи!

14

Знаменитая последовательность Фибоначчи 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

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

Нил А.
источник

Ответы:

2

На самом деле , 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.
Деннис
источник
Название языка делает его пассивно агрессивным.
Рохан
1
Я в этом сомневаюсь. Из-за этого комментария первая версия языка была названа серьезно . Для второй версии автор решил продолжать использовать прилагательные.
Деннис
6

Желе , 7 байт

ÆḞÆDÆḞS

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

Объяснение:

ÆḞÆDÆḞS Main link (Arguments: z)
ÆḞ      zth Fibonacci number's
  ÆD                           divisors'
    ÆḞ                                   Fibonacci numbers'
      S                                                     sum
Эрик Outgolfer
источник
Абсолютно возмутительно! Я не знаю ни одного из этих экзотических языков, но мне кажется сверхъестественным, как вы можете написать целый алгоритм с несколькими символами.
Богдан Александру
@BogdanAlexandru Вы можете видеть, что большинство используемых здесь встроенных модулей занимают 2 байта, поскольку они не помещаются в 1 байт. Смотрите Деннис на самом деле ответ для еще меньше символов. Кроме того, Jelly - это «язык игры в гольф», язык, созданный специально для Code-Golf , и он является одним из самых эффективных здесь (хотя не существует одного «самого эффективного» языка).
Эрик Outgolfer
Вы говорите, что эти языки не используются на практике и предназначены только для испытаний?
Богдан Александру
4

Mathematica, 29 байт

f=Fibonacci;f@#~DivisorSum~f&
Мартин Эндер
источник
4

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

Fi@#~Div9`~Fi&

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

Юнг Хван Мин
источник
Ну ... Используя более короткую версию того же языка ... Я думаю, это работает.
Нил А.
В Mathematica нет имен однобуквенных функций, верно? Не могли бы вы сопоставить все две строки символов, состоящие из первой заглавной буквы плюс один байт? В таком случае у вас было бы 26 * 256 = 6656 упрощенных 2-байтовых имен функций, что достаточно для 6356 имен 11.1.1 с 300 для резервирования.
Джонатан Аллан
@JonathanAllan Хорошая идея. (но есть функции с одним именем, например N)
JungHwan Min
2

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
Emigna
источник
2

Алиса , 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.
Мартин Эндер
источник
1

Аксиома, 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
RosLuP
источник
1

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)))
MickyT
источник
0

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
FrodCube
источник
0

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)

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

Arnauld
источник
0

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>

мохнатый
источник
Я думаю, что вы можете изменить (z=g(i)/y)>~~zна (z=g(i)/y)%1, если вы просто проверяете, что zэто целое число.
ETHproductions
@ETHproductions, что создает переполнение , которое может быть решено путем изменения g(z)в , g(z|0)но возвращает нас к тому же счетчику байтам.
Лохматый
0

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}
Дэниэл Плейнвью
источник