Ограничение этой программы для определения суммы обратных целых чисел, не содержащих ноль

Question

Пусть A обозначает набор натуральных чисел, десятичное представление которых не содержит цифру 0. Сумма обратных элементов в A известно как 23.10345.

Ex. 1,2,3,4,5,6,7,8,9,11-19,21-29,31-39,41-49,51-59,61-69,71-79,81-89, 91-99,111-119, ...

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

Как это можно проверить численно?

Напишите компьютерную программу для проверки этого номера.

Вот что я написал до сих пор, мне нужна помощь , ограничивающая эту проблему, так как в настоящее время она занимает слишком много времени:

Код на Java

import java.util.*; 

public class recip
{
    public static void main(String[] args)
    {
        int current = 0; double total = 0;

        while(total < 23.10245)
        {
            if(Integer.toString(current).contains("0"))
            {
                current++;
            }
            else
            {
                total = total + (1/(double)current);
                current++;
            }
            System.out.println("Total: " + total);
        }
    }
}

Answer 1

Это не так сложно при правильном подходе.

Предположим, например, что вы хотите найти сумму обратных значений всех целых чисел, начиная (то есть самые левые цифры) с 123 и заканчивая k ненулевыми цифрами. Очевидно, есть 9 ^k таких целых чисел, и обратная величина каждого из этих целых чисел находится в диапазоне 1 / (124 * 10 ^k ) .. 1 / (123 * 10 ^к ). Следовательно, сумма обратных величин всех этих целых чисел ограничена (9/10) ^k / 124 и (9/10) ^k / 123.

Чтобы найти границы для суммы всех обратных величин, начинающихся с 123, нужно сложить вышеуказанные оценки для каждого k> = 0. Это геометрическая серия, поэтому можно вывести, что сумма обратных целых чисел, начинающихся с 123, ограничена 10 * (9/10) ^k / 124 и 10 * (9/10) ^к / 123

Один и тот же метод, конечно, может применяться для любой комбинации крайних левых цифр. Чем больше цифр мы рассматриваем слева, тем точнее становится результат. Вот реализация этого подхода в Python:

def approx(t,k):
    """Returns a lower bound and an upper bound on the sum of reciprocals of
       positive integers starting with t not containing 0 in its decimal
       representation.
       k is the recursion depth of the search, i.e. we append k more digits
       to t, before approximating the sum. A larger k gives more accurate
       results, but takes longer."""
    if k == 0:
      return 10.0/(t+1), 10.0/t
    else:
        if t > 0:
            low, up = 1.0/t, 1.0/t
        else:
            low, up = 0, 0
        for i in range(10*t+1, 10*t+10):
            l,u = approx(i, k-1)
            low += l
            up += u
    return low, up

Например, вызов приближения (0, 8) дает нижнюю и верхнюю границу: 23.103447707 ... и 23.103448107 .... что близко к иску 23.10345, выданному ФП.

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

Answer 2

Как насчет сохранения текущего числа в виде байтового массива, где каждый элемент массива представляет собой цифру 0-9?Таким образом, вы можете очень быстро обнаружить нули (сравнивая байты, используя == вместо String.contains).

Недостатком будет то, что вам нужно будет реализовывать инкремент самостоятельно вместо использования ++.Вам также нужно будет придумать способ пометить «несуществующие» цифры, чтобы вы не определяли их как нули.Хранение -1 для несуществующих цифр звучит как разумное решение.

Answer 3

Я подозреваю, что приведение к строке и проверка на наличие символа '0' - это слишком длительный шаг. Если вы хотите избежать всех нулей, может помочь увеличить current таким образом:

(Отредактировано - благодаря Аарону МакСмуту)

current++;  
for( int i = 10000000; i >= 10; i = i / 10 )  
{
    if ( current % i ) == 0
    {
         current = current + ( i / 10 );
    }
}

Это не проверено, но концепция должна быть ясной: всякий раз, когда вы получаете кратное десятичной степени (например, 300 или 20000), вы добавляете следующую меньшую степень 10 (в наших примерах 10 + 1 и 1000 + 100 + 10 + 1 соответственно), пока в вашем номере больше не будет нулей.

Измените ваш цикл while соответствующим образом и посмотрите, не поможет ли вам производительность настолько, насколько ваша проблема станет управляемой.

О, и вы можете также немного ограничить вывод System.out. Будет ли достаточно каждой десятой, одной сотой или сотой итерации?

Редактировать второе: После некоторого сна я подозреваю, что мой ответ может быть немного недальновидным (обвините в позднем часе, если хотите). Я просто надеялся, что один миллион итераций current приведет вас к решению и оставит его на месте, вместо того, чтобы вычислять случаи коррекции, используя log( current ) и т. Д.

Если подумать, я вижу две проблемы со всей этой проблемой. Во-первых, ваш целевой номер 23.10345 - это игра на мой вкус. В конце концов, вы добавляете тысячи элементов, таких как «1/17», «1/11111» и т. Д., С бесконечными десятичными представлениями, и очень маловероятно, что они составят в точности 23,10345. Если кто-то из специалистов по вычислительной математике так и скажет, хорошо - но тогда я бы хотел увидеть алгоритм, по которому они пришли к такому выводу.

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

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

Редактировать третий: Из любопытства я написал это на C ++, чтобы проверить свои теории. Он работает в течение 6 минут и составляет около 14,5 (примерно 550 млн. Итераций). Посмотрим.

Текущая версия

double total = 0;
long long current = 0, currPowerCeiling = 10, iteration = 0;
while( total < 23.01245 )
{
    current++;
    iteration++;
    if( current >= currPowerCeiling )
        currPowerCeiling *= 10;

    for( long long power = currPowerCeiling; power >= 10; power = power / 10 )  
    {
        if( ( current % power ) == 0 )
        {
            current = current + ( power / 10 );
        }
    }
    total += ( 1.0 / current );

    if( ! ( iteration % 1000000 ) )
        std::cout << iteration / 1000000 << " Mio iterations: " << current << "\t -> " << total << std::endl;
}
std::cout << current << "\t" << total << std::endl;

Вычисление currPowerCeiling (или как бы это ни называли) вручную сохраняет некоторые вычисления log10 и pow на каждую итерацию. Каждый маленький кусочек помогает - но это все равно вечно ...

Редактировать четвертое: Состояние составляет около 66 000 миллионов итераций, общее количество - до 16.2583, время выполнения - около 13 часов. Не очень хорошо выглядит, Бобби С. - Я предлагаю более математический подход.

Answer 4

Для всех значений current, превышающих некоторый порог N, 1.0/(double)current будет достаточно маленьким, чтобы total не увеличивалось в результате добавления 1.0/(double)current. Таким образом, критерием завершения должно быть что-то вроде

 while(total != total + (1.0/(double)current))

вместо проверки по известному пределу a priori . Ваш цикл остановится, когда current достигнет этого специального значения N.

Answer 5

Для 32-разрядного целого числа со знаком эта программа никогда не остановится. Это на самом деле будет сходиться к -2097156. Так как максимальное число гармоник (сумма интегральных обратных значений от 1 до N) 32-разрядного целого числа со знаком равно ~14.66, этот цикл никогда не прекратится, даже если ток изменяется от 2^31 - 1 до -2^31. Поскольку обратная величина наибольшего отрицательного 32-разрядного целого числа равна ~ -4.6566e-10, каждый раз, когда ток возвращается к 0, сумма будет отрицательной. Учитывая, что наибольшее число, представимое double таким, что number + + 1/2^31 == number равно 2^52 / 2^31, вы получите примерно -2097156 в качестве сходящегося значения.

Сказав это, и предполагая, что у вас нет прямого способа вычисления номера гармоники произвольного целого числа, есть несколько вещей, которые вы можете сделать, чтобы ускорить свой внутренний цикл. Во-первых, самая дорогая операция будет System.out.println; это должно взаимодействовать с консолью, и в этом случае вашей программе в конечном итоге придется сбросить буфер на консоль (если есть). В некоторых случаях это может не произойти, но поскольку вы используете это для отладки, они не имеют отношения к этому вопросу.

Однако вы также тратите много времени на определение того, имеет ли число ноль. Вы можете перевернуть этот тест, чтобы сгенерировать диапазоны целых чисел, так что в этом диапазоне вы гарантированно не получите целое число с нулевой цифрой. Это очень просто сделать постепенно (в C ++, но достаточно просто для преобразования в Java):

class c_advance_to_next_non_zero_decimal
{
public:
    c_advance_to_next_non_zero_decimal(): next(0), max_set_digit_index(0)
    {
        std::fill_n(digits, digit_count, 0);

        return;
    }

    int advance_to_next_non_zero_decimal()
    {
        assert((next % 10) == 0);

        int offset= 1;
        digits[0]+= 1;

        for (int digit_index= 1, digit_value= 10; digit_index<=max_set_digit_index; ++digit_index, digit_value*= 10)
        {
            if (digits[digit_index]==0)
            {
                digits[digit_index]= 1;
                offset+= digit_value;
            }
        }

        next+= offset;

        return next;
    }

    int advance_to_next_zero_decimal()
    {
        assert((next % 10)!=0);
        assert(digits[0]==(next % 10));

        int offset= 10 - digits[0];
        digits[0]+= offset;
        assert(digits[0]==10);

        // propagate carries forward
        for (int digit_index= 0; digits[digit_index]==10 && digit_index<digit_count; ++digit_index)
        {
            digits[digit_index]= 0;
            digits[digit_index + 1]+= 1;

            max_set_digit_index= max(digit_index + 1, max_set_digit_index);
        }

        next+= offset;
        return next;
    }

private:
    int next;

    static const size_t digit_count= 10; // log10(2**31)

    int max_set_digit_index;

    int digits[digit_count];
};

То, что делает код выше, состоит в том, чтобы выполнять итерацию по каждому диапазону чисел так, чтобы этот диапазон содержал только числа без нулей. Он работает, определяя, как перейти от N000 ... к N111 ... и от N111 ... до (N + 1) 000 ..., перенеся (N + 1) в 1 (0) 000 ..., если необходимо.

На моем ноутбуке я могу сгенерировать номер гармоники 2 ^ 31 - 1 за 8,73226 секунд.

Answer 6

public class SumOfReciprocalWithoutZero {
public static void main(String[] args) {

    int maxSize=Integer.MAX_VALUE/10;
    long time=-System.currentTimeMillis();
    BitSet b=new BitSet(maxSize);
    setNumbersWithZeros(10,maxSize,b);

    double sum=0.0;
    for(int i=1;i<maxSize;i++)
    {
        if(!b.get(i))
        {
            sum+=1.0d/(double)i;
        }
    }
    time+=System.currentTimeMillis();
    System.out.println("Total: "+sum+"\nTimeTaken : "+time+" ms");


}

 static void setNumbersWithZeros(int srt,int end,BitSet b)
 {
        for(int j=srt;j<end;j*=10)
        {
            for(int i=1;i<=10;i++)
        {
            int num=j*i;
            b.set(num);
        }
            if(j>=100)
            setInbetween(j, b);
        }
 }

 static void setInbetween(int strt,BitSet b)
 {

     int bitToSet;
     bitToSet=strt;
     for(int i=1;i<=10;i++)
     {
      int nxtInt=-1;

     while((nxtInt=b.nextSetBit(nxtInt+1))!=strt)
     {
         b.set(bitToSet+nxtInt);
     }
     nxtInt=-1;
     int lim=strt/10;
     while((nxtInt=b.nextClearBit(nxtInt+1))<lim)
     {
         b.set(bitToSet+nxtInt);
     }

     bitToSet=strt*i;

     }
 }


}

Это реализация, использующая BitSet. Я вычислил сумму обратных значений для всех целых чисел в диапазоне (1-Integer.MAX_VALUE/10). Сумма достигает 13.722766931560747. Это максимальное значение, которое я мог бы рассчитать с помощью BitSet, поскольку максимальный диапазон для BitSet равен Integer .MAX_VALUE. Мне нужно разделить его на 10 и ограничить диапазон, чтобы избежать переполнения. Но есть значительное улучшение в скорости. Я просто публикую этот код на тот случай, если он может дать вам новую идею по улучшению вашего кода. (Увеличьте Ваша память, используя аргумент VM -Xmx[Size>350]m)

Выход:

Total: 13.722766931560747
TimeTaken : 60382 ms

UPDATE:

Портирование Java предыдущего, удаленного ответа:

     public static void main(String[] args) {
        long current =11;
        double tot=1 + 1.0/2 + 1.0/3 + 1.0/4 + 1.0/5 + 1.0/6 + 1.0/7 + 1.0/8 + 1.0/9;
        long i=0;
        while(true)
        {
            current=next_current(current);
            if(i%10000!=0)
                System.out.println(i+" "+current+" "+tot);
            for(int j=0;j<9;j++)
            {
                tot+=(1.0/current + 1.0/(current + 1) + 1.0/(current + 2) + 1.0/(current + 3) + 1.0/(current + 4) +
                          1.0/(current + 5) + 1.0/(current + 6) + 1.0/(current + 7) + 1.0/(current + 8));

                current += 10;
            }
            i++;
        }

    }

    static long next_current(long n){

    long m=(long)Math.pow(10,(int)Math.log10(n));
    boolean found_zero=false;
    while(m>=1)
    {
        if(found_zero)
            n+=m;
        else if((n/m)%10==0)
        {
            n=n-(n%m)+m;
           found_zero=true;
        }

     m=m/10;
    }
    return n;
    }