Есть ли способ найти приблизительное значение n-го числа?

Есть ли функция, которая вернет приблизительное значение nth prime? Я думаю, что это будет нечто вроде приближенной инверсной функции подсчета. Например, если бы я дал эту функцию 25, он вернул бы число около 100, или если бы я дал эту функцию 1000, он вернул бы число около 8000. Меня не волнует, является ли число возвращено простым или нет, но я действительно хочу он должен быть быстрым (поэтому нет генерации первых n простых чисел для возврата n-го.)

Мне бы хотелось, чтобы я мог генерировать первые n простых чисел, используя сито (Eratosthenes или Atkin). Поэтому аппроксимация для n th идеально никогда не будет недооценивать значение фактического nth простого.

(Update: см. мой ответ для хорошего метода нахождения верхней границы n-го простого числа.)

Ответ 1

Более жесткие ограничения:

static const unsigned short primes_small[] = {0,2,3,5,7,11};

static unsigned long nth_prime_upper(unsigned long n) {
  double fn = (double) n;
  double flogn, flog2n, upper;
  if (n < 6)  return primes_small[n];
  flogn  = log(n);
  flog2n = log(flogn);

  if      (n >= 688383)    /* Dusart 2010 page 2 */
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn));
  else if (n >= 178974)    /* Dusart 2010 page 7 */
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn));
  else if (n >=  39017)    /* Dusart 1999 page 14 */
    upper = fn * (flogn + flog2n - 0.9484);
  else                    /* Modified from Robin 1983 for 6-39016 _only_ */
    upper = fn * ( flogn  +  0.6000 * flog2n );

  if (upper >= (double) ULONG_MAX) {
     /* Adjust this as needed for your type and exception method */
    if (n <= 425656284035217743UL) return 18446744073709551557UL;
    fprintf(stderr, "nth_prime_upper overflow\n"; exit(-1);
  }

  return (unsigned long) ceil(upper);
}

Они никогда не должны быть меньше фактического nth_prime, должны работать для любого 64-битного ввода и быть на порядок или ближе по сравнению с формулой из Robin, приведенной ранее (или Wimblik сложная ограниченная по диапазону формула). Для моего использования у меня есть немного более крупный маленький столбец, поэтому можно немного подтянуть последнюю оценку. Технически из формул мы могли бы использовать floor() вместо ceil(), но я беспокоюсь о точности.

Изменить: Еще один вариант для улучшения этого бита - это реализация хороших границ графа (например, Axler 2014) и выполнение на них двоичного поиска. Мой код для этого метода занимает ~ 10 раз больше, чем указано выше (все еще работает в миллисекундах), но может уменьшить процент ошибки на порядок.

Если вам нужна оценка для n-го числа, вы можете сделать:

Cipolla 1902 (см. Dusart 1999 страница 12 или этот документ. Я нахожу три слагаемых (m = 2) плюс поправочный коэффициент третьего порядка, который полезен, но с большим количеством членов он колеблется слишком сильно. Формула, показанная в ссылке Википедии, является этой формулой (с m = 2). двухчленный обратный или обратный Риман R ниже даст лучшие результаты.
Рассчитайте верхнюю и нижнюю границы Dusart 2010 и усредните результаты. Не так уж плохо, хотя я подозреваю, что использование взвешенного среднего будет работать лучше, поскольку границы не одинаково плотны.
li ^ {- 1} (n) Так как li (n) является приличной аппроксимацией простого числа, обратное является достойным аппроксимацией nth_prime. Это и все остальное можно сделать довольно быстро, как двоичный поиск функции.
li ^ {- 1} (n) + li ^ {- 1} (sqrt (n))/4 Ближе, поскольку это приближается к R (n)
R ^ {- 1} Обратная функция Римана R является ближайшим средним приближением. Я знаю, что разумно.

Наконец, если у вас очень быстрый метод подсчета числа, например, одна из реализаций LMO (теперь есть три реализации с открытым исходным кодом), вы можете написать быстрый точный метод nth_prime. Вычисление 10 ^ 10-го числа может быть выполнено за несколько миллисекунд, а 10-13-е через пару секунд (на современной быстрой машине). Приближения чрезвычайно быстрые на всех размерах и работают для гораздо большего числа, но все имеют другое представление о том, что означает "большой".

Ответ 2

Спасибо за все ответы. Я подозревал, что есть что-то довольно простое, но в то время я не мог найти его. Я сделал еще немного исследований.

Как я хочу, для sieve для генерации первых n простых чисел, я хочу, чтобы приближение было больше или равно nth prime. (Поэтому я хочу верхнюю оценку n-го простого числа.)

Wikipedia дает следующую верхнюю границу для n >= 6

p_n <= n log n + n log log n   (1)

где p_n - n-е правое, а log - натуральный логарифм. Это хорошее начало, но он может переоценить незначительную сумму. Эта статья в Журнал математики колледжа дает более жесткий верхняя граница для n >= 7022

p_n <= n log n + n (log log n - 0.9385)   (2)

Это гораздо более жесткая привязка, как показано в следующей таблице.

n         p_n         approx 1    error%  approx 2    error%
1         2                            
10        29          31          6.90 
100       541         613         13.31
1000      7919        8840        11.63
10000     104729      114306      9.14    104921      0.18
100000    1299709     1395639     7.38    1301789     0.16
1000000   15485863    16441302    6.17    15502802    0.11
10000000  179424673   188980382   5.33    179595382   0.10

Я применил функцию n-го первого приближения для использования второго приближения для n >= 7022, первого приближения для 6 <= n < 7022 и поиска массива для первых 5 простых чисел.

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

Ответ 3

Теорема о типовом номере дает ряд простых значений ниже порогового значения, поэтому его можно было использовать, чтобы дать приблизительное значение для n-го простого числа.

Ответ 4

В качестве приблизительной оценки вы можете использовать n * ln (n) в качестве приближения для n-го простого числа. Существует гораздо более сложный, но более точный метод, подробности которого вы можете найти в Википедии здесь.

Ответ 5

Мой лучший премьер (n) Оценка

1/2*(8-8.7*n-n^2+
1/2*(2*abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+
abs((log(log(3))-log(log(n))+2*n*log(log(n)/log(2))+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2))))/log(log(n)/log(2))))*(-1+
abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+abs(-(1/2)+n+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2)))/(2*log(log(n)/log(2))))))

Вот моя самая последняя экспериментальная формула. Кстати. Десять триллионных простых чисел 323,780,508,946,331 эта формула работает довольно хорошо в этом масштабе, не уверен, что она продолжает приближаться, чем n*ln(n)+n*(ln(ln(n))-0.9385).

1/2*(3-(8+ln(2.3))*n-n^2+1/2*(-1+
abs(-(1/2)+n+sqrt(ln(ln(n)/ln(2))*(-ln(ln(2))+ln(ln(n))+
(8*ln(3)*ln((n*ln(8*n))/ln(n)))/ln(2)))/(2*ln(ln((n*ln(8*n))/
ln(n))/ln(2))))+abs(ln(n)/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ln(2))/
ln(2)))*(2*abs(ln((n*ln(8*n))/ln(n))/ln(3)+ln(ln((n*ln(8*n))/ln(n))/
ln(2))/ln(2))+abs(1/ln(ln(n)/ln(2))*(ln(ln(3))-ln(ln(n))+2*n*ln(ln(n)/
ln(2))+sqrt(((8*ln(3)*ln(n))/ln(2)-ln(ln(2))+ln(ln((n*ln(8*n))/ln(n))))*
ln(ln((n*ln(8*n))/ln(n))/ln(2)))))))

Ответ 6

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

Ваше собственное вложение в этот вопрос и мой ответ - это хорошие способы реализовать это, не зная appr, значение простого

Ответ 7

Чтобы дополнить Dana J Upper, эта формула должна дать вам хорошую нижнюю границу.

P(n) = (((2 Log(3, n + 2))/(Log(2.5, 2) + Log(3, 3)) + (2 Log(3, n - 2))/(Log(3, 2) + Log(3, 3)))/2) n;

Ответ 8

Вы можете найти формулу для нахождения n-го индекса, используя теорему простого числа. Вот как https://azizl.github.io Оформить заказ в первом посте