Формула числового ряда 1, 2, 5, 10, 20, 50

Question

Есть бесконечная последовательность "красивых чисел":

... 0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1, 2, 5, 10, 20, 50, ...

Как для произвольного числа x, 1e-10 < x < 1e+10 найти следующее за ним "красивое" число?

Answer 1

Простая идея такая. Пусть данное число x.

1. Находим десятичный логарифм числа. Округляем его вниз (floor) до целого, пусть результат будет n.
2. Вычисляем 10 в степени n (умножением или через экспоненту), получаем N. Число N является степенью десятки, причём N ⩽ x < 10N.
3. Это значит, что искомое число — одно из N, 2N и 5N. Сравниваем x с N, 2N и 5N, находим результат.

---

4. В принципе, из-за проблем с точностью вычислений с плавающей запятой мы могли получить в шаге 2 неправильный N. Поэтому, возможно, имеет смысл добавить в шаг 2 ещё две проверки:
   • если x оказалось меньше N, уменьшить n на единицу и повторить шаг 2 (или просто разделить N на 10 и перепроверить)
   • если x оказалось больше или равно 10N, увеличить n на единицу и повторить шаг 2 (или просто умножить N на 10 и перепроверить).

Answer 2

Python, itertools

Наивная реализация: делаем последовательность [..., 0.1, 0.2, 0.5, 1, 2, ...].

Берем range(-10, 10) и отображаем его в [..., 0.01, 0.1, 1, 10, ...]
Перемножаем множества [1, 2, 5] и [... 0.1, 1, 10, ...] - получаем [..., (1, 0.1), (2, 0.1), (5, 0.1), (1, 1), (2, 1), ...].
Перемножаем элементы каждого кортежа - из (5, 0.1) получается 0.5.
Находим первый элемент, которые больше x:

from itertools import *
from operator import *
from math import *
def next_pretty_number(x):
    exp10 = lambda x: pow(10, x)
    powers_of_10 = map(exp10, range(-10, 10)) # ...0.01, 0.1, 1, 10, ...
    seq = starmap(mul, product([1, 2, 5], powers_of_10))
    return next(dropwhile(lambda y: y < x, seq))

Правильная реализация:
Вся последовательность от 1e-10 до 1e+10 нам не нужна. Достаточно взять десятичный порядок x и умножить на него [1, 2, 5, 10]:

def next_pretty_number(x):
    scale = 10**floor(log10(x))
    seq = [scale*1, scale*2, scale*5, scale*10]
    return next(dropwhile(lambda y: y < x, seq))

C++

Алгоритм на Python можно переписать на С++, сохранив такую же выразительность:

auto scale = pow(10, floor(log10(x)));
double seq[] = {scale*1, scale*2, scale*5, scale*10};
auto next_pretty_number = *std::lower_bound(seq, seq+4, x);

Answer 3

C, по мотивам oeis.org/A051109

Берем элементы из списка [1,2,5] так что индекс элемента - остаток от деления некоторого числа n на длину списка, и домножаем их на pow(10, n/3).

Так как n может быть отрицательно, надо добавлять смещение чтобы операции % и / производились над положительными числами (подробнее тут).

В С и С++ вместо списка целых чисел можно взять строковый литерал.

double next_pretty_number(double x) {
    double result = 1e-10;
    for (auto n = -30; result < x; ++n)
      result = "\x1\x2\x5"[(30 + n) % 3] * pow(10, (30 + n) / 3 - 10);
    return result;
}

Answer 4

Можно сформировать множитель к текущему числу.

Известно, что: log10(1) = 0, log10(2) = 0.3, log10(5) = 0,7.
При умножении этих чисел на положительную или отрицательную степень 10 дробная часть логарифма будет та же самая.

Умножая её на 4 и округляя по недостатку, получим индекс 0, 1, 2.
Для индексов 0 и 2 множитель 4/2, для индекса 1 - множитель 5/2.

Программа (PHP):

function next_nice(&$n){
    $db = log10($n);                    // логарифм
    $frac = $db - floor($db);           // дробная часть
    $ind = (int)floor(4*$frac);         // индекс
    $n = $n * (5 - abs($ind-1)) / 2 ;   // умножение
    printf ("<br>next = %.9f", $n);
    return $n;
}

$n = 0.000000001;
while(next_nice($n) < 1E9);

Результаты:

next = 0.000000002
next = 0.000000005
next = 0.000000010
next = 0.000000020
next = 0.000000050
next = 0.000000100
next = 0.000000200
next = 0.000000500
next = 0.000001000
next = 0.000002000
next = 0.000005000
next = 0.000010000
next = 0.000020000
next = 0.000050000
next = 0.000100000
next = 0.000200000
next = 0.000500000
next = 0.001000000
next = 0.002000000
next = 0.005000000
next = 0.010000000
next = 0.020000000
next = 0.050000000
next = 0.100000000
next = 0.200000000
next = 0.500000000
next = 1.000000000
next = 2.000000000
next = 5.000000000
next = 10.000000000
next = 20.000000000
next = 50.000000000
next = 100.000000000
next = 200.000000000
next = 500.000000000
next = 1000.000000000
next = 2000.000000000
next = 5000.000000000
next = 10000.000000000
next = 20000.000000000
next = 50000.000000000
next = 100000.000000000
next = 200000.000000000
next = 500000.000000000
next = 1000000.000000000
next = 2000000.000000000
next = 5000000.000000000
next = 10000000.000000000
next = 20000000.000000000
next = 50000000.000000000
next = 100000000.000000000
next = 200000000.000000000
next = 500000000.000000000
next = 1000000000.000000000