Алгоритм вычисления k долей формы 1/r суммирования до 1

Ответ 1

Если все, что вы хотите сделать, это найти самый большой знаменатель, нет никаких причин для поиска всех возможностей. Вы можете сделать это очень просто:

public long largestDenominator(int k){
    long denominator = 1;
    for(int i=1;i<k;i++){
        denominator *= denominator + 1;
    } 
    return denominator;
}

Для рекурсивных типов:

public long largestDenominator(int k){
    if(k == 1)
        return 1;
    long last = largestDenominator(k-1);
    return last * (last + 1); // or (last * last) + last)
}

Почему это так просто?

Чтобы создать набор, вам нужно вставить самую большую дробь, которая будет хранить ее под 1 на каждом шаге (кроме последнего). Под "большой долей" я имею в виду значение, означая наименьший знаменатель.

Для простого случая k=3 это означает, что вы начинаете с 1/2. Вы не можете подобрать другую половину, так что вы идете с 1/3. Затем 1/6 остается, предоставляя вам три слова.

В следующем случае k=4 вы берете 1/6 с конца, так как он не подпадает под один, и нам нужно место для другого термина. Замените его 1/7, так как это самое большое значение, которое подходит. Остальная часть 1/42.

Повторите при необходимости.

Например:

• 2: [2,2]
• 3: [2,3,6]
• 4: [2,3,7,42]
• 5: [2,3,7,43,1806]
• 6: [2,3,7,43,1807,3263442]

Как вы можете видеть, он быстро становится очень большим. Достаточно быстро, чтобы вы переполнили long, если k>7. Если вам нужно это сделать, вам нужно будет найти соответствующий контейнер (например, BigInteger в Java/С#).

Он отлично отображает эту последовательность:

a(n) = a(n-1)^2 + a(n-1), a(0)=1.

Вы также можете увидеть отношение к последовательность Сильвестра:

a(n+1) = a(n)^2 - a(n) + 1, a(0) = 2

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

Ответ 2

Я никогда не слышал о египетских фракциях, но вот несколько мыслей:

Идея

Вы можете думать о них геометрически:

• Начните с квадрата единицы (1x1)
• Нарисуйте вертикальные или горизонтальные линии, разделяющие квадрат на равные части.
• Повторяйте произвольное рисование строк внутри любого из подборок равномерно.
• Остановитесь в любое время.

Представленные прямоугольники образуют набор дробей вида 1/n, которые добавляют к 1.

Вы можете подсчитать их, и они могут равняться вашему "k".

В зависимости от того, сколько равных разделов вы разделили прямоугольник, в нем будет указано, есть ли у вас 1/2 или 1/3 или что-то еще. 1/6 составляет 1/2 1/3 или 1/3 1/2. (т.е. вы нырнули на 2, а затем один из подборок на 3 ИЛИ наоборот).

Идея 2

Вы начинаете с 1 окна. Это доля 1/1 с k = 1.

Если вы разделите n на n, вы добавите n к числу полей (k или суммированных сумм) и вычтите 1.

Когда вы разделите один из этих полей, снова вычтите 1 и добавьте n, количество делений. Обратите внимание, что n-1 - это количество строк, которые вы нарисовали, чтобы разделить их.

Подробнее

Вы начнете поиск ответа с помощью k. Очевидно, k * 1/k = 1, поэтому у вас есть одно решение.

Как насчет k-1?

Там есть решение: (k-2) * 1/(k-1) + 2 * (1/((k-1) * 2))

Как я понял? Я сделал k-1 равных частей (с k-2 вертикальными линиями), а затем разделил последний пополам по горизонтали.

Каждое решение будет состоять из:

• принимая предварительное решение
• используя j меньше строк и некоторую стадию, и разделив один из ящиков или под-ящиков на j + 1 равные секции.

Я не знаю, могут ли быть сформированы все решения, повторяя это правило, начиная с k * 1/k

Я знаю, что вы можете получить эффективные дубликаты таким образом. Например: k * 1/k с j = 1 = > (k-2) * 1/(k-1) + 2 * (1/((k-1) * 2)) [сверху], но k * 1/k с j = (k-2) = > 2 * (1/((k-1) * 2)) + (k-2) * 1/(k-1) [который просто меняет порядок части]

Интересный

k = 7 может быть представлено 1/2 + 1/4 + 1/8 +... + 1/(2 ^ 6) + 1/(2 ^ 6), а общий случай равен 1/2 +... + 1/(2 ^ (k-1)) + 1/(2 ^ (k-1)).

Аналогично для любого нечетного k его можно представить в виде 1/3 +... + 3 * [1/(3 ^ ((k-1)/2)].

Я подозреваю, что существуют похожие шаблоны для всех целых чисел до k.