Создайте функцию, выражение или программу, которая выполняет следующие действия:

1. Возьмите главные факторы любого числа и суммируйте их. Например, главные факторы 28 - 2 2 7, суммированные к 11.
2. Умножьте результат на число простых факторов для данного числа. Например, 28 имеет 3 основных фактора, которые составляют 11. 11 * 3 - 33.
3. Повторяйте процесс рекурсивно, сохраняя результирующий список (который начинается с исходного номера), пока не достигнете номера, который уже включен в список. Остановите без добавления этого последнего номера, чтобы в списке не было дубликатов. Прогрессия для 28 составляет 28 33, потому что 33 приводит к 28 снова.
4. Подсчитайте элементы в результирующем списке. В случае 28 ответ 2.

Вот результаты для 0<n<=10, так что вы можете проверить свой алгоритм.

2 1 1 10 1 11 1 9 5 10

(Как указал Бальфа, ответ на этот вопрос higley(1)- 2 из списка 1 0. У меня изначально было 1, из-за ошибки в моем оригинальном алгоритме, написанном на J.)

Поскольку я тщеславный SOB и не нашел этого в OEIS , давайте назовем это «Последовательностью Хигли», по крайней мере, на время этого раунда гольф-кода. В качестве дополнительного бонуса, найдите первые два, nимеющие самые низкие, higley(n)где nне простое и n>1. (Я думаю, что есть только два, но я не могу доказать это.)

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

J, 47 45

#@((~.@,[:(+/@{:*+/@:*/)2 p:{:)^:_)`2:@.(=&1)

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

Изменить: (47-> 45) День двойного купона.

Применение:

   higley =: #@((~.@,(+/@{:*+/@:*/)@(2&p:)@{:)^:_)`2:@.(=&1)
   higley 1
2
   higley"0 (1 + i. 10)
2 1 1 10 1 11 1 9 5 10

Golfscript, 68 67 62 61 символ

[.]({[.2@{1$1$%{)}{\1$/1$}if}*;;].,*0+{+}*.2$?@@.@+\@)!}do;,(

Это выражение: оно берет nстек и оставляет результат в стеке. Чтобы превратить его в программу, которая берет nиз stdin и печатает результат в stdout, замените ведущий [на~

Суть его [.2@{1$1$%{)}{\1$/1$}if}*;;](28 символов) занимает верхнее число в стеке и (по невероятно неэффективному алгоритму) генерирует список его основных факторов. Эквивалент псевдокода в стиле C:

ps = [], p = 2;
for (int i = 0; i < n; i++) {
    if (n % p == 0) {
        ps += p;
        n /= p;
    }
    else p++;
}

0+Непосредственно перед {+}*это обработать особый случай n==1, потому что Golfscript не как складывание бинарной операции над пустым списком.

Одна из непростых точек привязки - 27; Я нашел это, не используя программу, рассматривая сопоставление (p ^a -> a ² p), которое является фиксированной точкой, если a == p ^{(a-1) / 2} , и пробует мало a. ( a==1дает фиксированность простых чисел).

Поиск с помощью программы приводит к появлению второй точки фиксации: 30 = (2 + 3 + 5) * 3

Приложение: доказательство того, что есть только две не простые фиксированные точки

Обозначение: sopfr(x)сумма простых множителей xс повторением (A001414). Omega(x)число простых факторов x(A001222). Таким образом, функция преемника Хиглиh(x) = sopfr(x) Omega(x)

Предположим, у нас есть фиксированная точка, N = h(N)которая является продуктом n=Omega(N)простых чисел.

N = p_0 ... p_{n-1} = h(N) = n (p_0 + ... + p_{n-1})

Основная теория чисел: nделится на p_0 ... p_{n-1}, поэтому w=Omega(n)эти простые числа являются главными факторами n. Wlog мы возьмем их, чтобы быть последним w. Таким образом, мы можем разделить обе стороны nи получить

p_0 ... p_{n-w-1} = p_0 + ... + p_{n-1}

или

p_0 ... p_{n-w-1} = p_0 + ... + p_{n-w-1} + sopfr(n)

Учитывая , что все простые числа , p_0чтобы p_{n-w-1}больше 1, увеличение любого из них увеличивает на LHS больше , чем ОРЗ. Таким образом, для данного nмы можем перечислить все варианты решения.

В частности, не может быть никаких решений, если LHS больше, чем RHS, устанавливая все «свободные» простые числа в 2. Т.е. не существует решений, если

2^{n-w} > 2 (n-w) + sopfr(n)

Поскольку sopfr(n) <= n(с равенством только для n = 4 или n простых), мы можем сделать более слабое утверждение, что нет фиксированных точек, если

2^{n-w} > 3 n - 2 w

Держа wфиксированными, мы можем выбрать различные значения nудовлетворения w=Omega(n). Наименьшее такое nесть 2^w. Обратите внимание, что если 2^{n-w}по крайней мере 3 (т.е. если n-w>1, что верно, если n>2), то увеличение nпри wсохранении постоянной увеличит LHS больше, чем RHS. Отметим также, что для w>2и принимая наименьшее возможное nнеравенство выполняется, и нет никаких фиксированных точек.

Это оставляет нам три случая: w = 0и n = 1; w = 1и nпростое; или w = 2и nполуместно.

Случай w = 0. n = 1Как и Nлюбое простое.

Случай w = 1. Если n = 2тогда N = 2pи мы требуем p = p + 2, который не имеет решений. Если n = 3тогда у нас есть pq = p + q + 3и два решения, (p=2, q=5)и (p=3, q=3). Если n = 5тогда 2^4 > 3 * 5 - 2 * 1, значит, дальнейших решений нет w = 1.

Случай w = 2. Если n = 4тогда N = 4pqи мы требуем pq = p + q + 4. Здесь есть целочисленное решение p=2, q=6, но нет простых решений. Если n = 6тогда 2^4 > 3 * 6 - 2 * 2, значит, дальнейших решений нет w = 2.

Все случаи исчерпаны, поэтому единственными непростыми фиксированными точками являются 27 и 30.

Рубин, 92 символа

f=->i{r=[i];(x=s=0;(2..i).map{|j|(s+=j;x+=1;i/=j)while i%j<1};r<<i=s*x)until r.uniq!;r.size}

Это решение предполагает, что Higley (1) на самом деле равно 2, а не 1 (см. Комментарий Бальфы выше):

(1..10).map &f
=> [2, 1, 1, 10, 1, 11, 1, 9, 5, 10]

Октава - 109 символов

l=[input('')];while size_equal(unique(l),l);n=factor(l(1));l=[sum(n)*length(n) l];endwhile;disp(length(l)-1);

MATL , 19 байт

i`vt0)Yftnws*yy-]xn

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