Константа Бруна - это значение, к которому сходится сумма обратных величин двойных простых пар ( 1/p
и 1/(p+2)
где p
и p+2
оба являются простыми). Это примерно 1.902160583104
.
Учитывая положительное целое число N
, аппроксимируйте постоянную Бруна путем суммирования обратных величин пар двойников простых чисел, где оба простых числа в паре меньше N
, и выведите приближение.
правила
N
будет положительным целым числом в пределах представимого диапазона для вашего языка.- Вывод должен быть как можно точнее до истинного значения, в пределах реализации вашего языка с плавающей запятой, игнорируя любые потенциальные проблемы из-за арифметических неточностей с плавающей запятой. Если ваш язык допускает арифметику с произвольной точностью, он должен быть как минимум настолько же точным, как арифметика с двойной точностью IEEE 754.
- В качестве альтернативы, точная дробь может быть выведена в любом непротиворечивом, однозначном формате.
- Если простое число появляется в нескольких двойных простых парах (например
5
, часть обоих(3, 5)
и(5, 7)
), его обратный вклад в сумму каждый раз.
Тестовые случаи
2 -> 0
6 -> 0.5333333333333333
10 -> 0.8761904761904762
13 -> 0.8761904761904762
100 -> 1.3309903657190867
620 -> 1.4999706034568274
100000 -> 1.67279958482774
Ответы:
Python 3 ,
787775706862 байтаСпасибо @xnor за игру в гольф
24 байта и проложил путь еще 4!Попробуйте онлайн!
Задний план
Напомним, что теорема Вильсона утверждает, что для всех целых чисел k> 1 ,
где a ≡ b (mod d) означает, что a - b делится на d равномерно , т. е. a и b имеют одинаковый остаток при делении на d .
В теоремах Вильсона для двойных, гипер-, суб- и супер-факториалов авторы доказывают обобщения для двойных факториалов, на которых основывается этот ответ. Двойной факториал целого числа к ^ 0 определяется
Теорема 4 вышеупомянутой статьи утверждает следующее.
Повышая обе стороны сравнений до четвертой степени, мы выводим, что
для всех нечетных простых чисел р . С 1 года !! = 1 , эквивалентность верна и для p = 2 .
Теперь, делая то же самое с теоремой Уилсона,
поскольку
следует, что
всякий раз, когда р простое.
Теперь пусть k будет нечетным, положительным, составным целым числом. По определению существуют целые числа a, b> 1, такие что k = ab .
Так как k нечетно, то и a и b . Таким образом, оба встречаются в последовательности 1, 3,…, k - 2 и
где | указывает на делимость.
Суммируя, для всех нечетных целых чисел k> 1
где p (k) = 1, если k простое, и p (k) = 0, если k составное.
Как это работает
Когда функция f вызывается с одним аргументом, k , m и j инициализируются как 3 , 1 и 0 .
Обратите внимание, что ((k - 2) !!) 4 = 1 !! 4 = 1 = т . Фактически, равенство m = ((k - 2) !!) 4 будет выполняться всегда. j является плавающей точкой и всегда будет равно ((k - 4) !!) 4 % (k - 2) / (k - 2) .
В то время как k <n , правильный аргумент
and
будет оценен. Поскольку j = ((k - 4) !!) 4 % (k - 2) / (k - 2) , как доказано в первом абзаце, j = 1 / (k - 2), если k - 2 простое и j = 0, если нет. Аналогично, поскольку m% k = ((k - 2) !!) 4 равно 1, если k простое, и 0, если нет, -m% k = k - 1, если простое k, и -m% k = 0, если нет. Следовательно,-m%k*j*2/k
оценивается как 2 (k - 1) / (k (k - 2)) = ((k - 2) + k) / (k (k - 2)) = 1 / k + 1 / (k - 2) если пара (k - 2, k)состоит из двух простых чисел и 0, если нет.Вычислив вышеизложенное, мы добавляем результат к возвращаемому значению рекурсивного вызова
f(n,k+2,m*k**4,m%k/k)
. k увеличивается на 2, поэтому он принимает только нечетные значения ‡ † , мы умножаем m на k 4, поскольку mk 4 = ((k - 2) !!) 4 k 4 = (k !!) 4 , и передаем текущее значение m% k / k - что равно 1 / k, если «старое» k - простое число, и 0, если нет - как параметр j для вызова функции.Наконец, когда k равно или больше n , f возвращает False, и рекурсия прекращается. Возвращаемое значение f (n) будет суммой всех 1 / k + 1 / (k - 2), таких (k - 2, k) - двойная простая пара, и k <n , по желанию.
‡ Результаты из абзаца Background сохраняются только для нечетных целых чисел. Поскольку даже целые числа не могут быть двойными простыми числами, мы можем их безопасно пропустить.
источник
m%k*(j/k+j/(k-2))
.((k-2)!!)^4 = p(k)
по модулюp
для странныхp
. Я не проработал ваш аргумент, но вот тот, который я придумал (по сути это может быть то же самое). Работа по модулюp
в сете{1,2,..,p-1}
, четные моменты - это как раз отрицательные шансы. Так,prod(odds) = ± prod(evens)
. Теорема Уилсона говорит нам об этомprod(all) = - p(k)
. Так какprod(all) = prod(odds) * prod(evens) = prod(odds) * ± prod(evens)
у насprod(odds)^2 = ±p(k)
и такprod(odds)^4 = p(k)^2 = p(k)
.Желе ,
1514 байтПопробуйте онлайн!
Как это работает
источник
Желе ,
1614 байт (с небольшой помощью @Dennis)Попробуйте онлайн!
Пытаясь улучшить свой предыдущий ответ, я придумал совершенно другой алгоритм, и он несколько короче. Я использую для этого другой пост, как здесь стандарт для ответа, который использует другую технику.
Денис предлагает заменить
_/2+$$Ðḟ
наIċ¥Ðf2
; Я полностью забыл о возможности диадического фильтра. Таким образом, этот алгоритм теперь связан с тем, который использовал ответ Денниса.объяснение
источник
2_/2+$$Ðḟ
может статьIċ¥Ðf2
.Брахилог , 17 байт
Попробуйте онлайн!
Это совершенно новая версия Brachylog, с блестящей кодовой страницей!
объяснение
источник
MATL , 16 байт
Попробуйте онлайн!
Рассмотрим ввод
13
в качестве примера.источник
Mathematica,
4847 байтовСпасибо JungHwan Min за сохранение 1 байта!
Безымянная функция, принимающая положительное целое число в качестве входных данных и возвращающая точную дробь; например,
If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&[10]
возвращает92/105
.If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]
проверяет, являются ли обаi
иi-2
простыми, возвращая сумму их взаимных значений, если так, а0
если нет.~Sum~{i,#-1}&
затем возвращает сумму этих вкладов для всех значенийi
меньше, чем вход.Предыдущее представление:
источник
If[PrimeQ/@(i&&(g=i-2)),1/i+1/g,0]~Sum~{i,#-1}&
N@
перед кодом.N
возвращает десятичное приближение к реальному числу; однако для отображения более 6 сиг-фиг требуется около байтов, и независимо от того, сколько отображается сиг-фиг, он все равно менее точен, чем сама дробь.Октава, 45 байт
Объяснение:
Попробуйте онлайн!
источник
JavaScript (ES6),
6766 байтСохранено 1 байт благодаря @Arnauld
Выходы
false
для тестового примера2
, который разрешен по умолчанию .Тестовый фрагмент
Показать фрагмент кода
источник
1/n+++1/++n
сохраняет байт.+++
это не всегда05AB1E ,
1914 байтов (-5 @Emigna)Попробуйте онлайн!
источник
<LDpÏÍDpÏDÌ«zO
сохранить 5 байтов.Желе , 19 байт
Попробуйте онлайн!
У меня такое чувство, что это невозможно, но я не могу сразу понять, как это сделать.
объяснение
В
µ
Соедините все эти части вместе трубопровода типа, с каждый из которых принимает выход один перед тем, как его вход.источник
Pyth -
222117 байтЯ думаю, что рефакторинг поможет.
Тестовый пакет .
источник
Perl 6 ,
5951 байт{sum 1 «/»grep((*-(2&0)).is-prime,^$_).flatmap:{$_-2,$_}}
-2..* Z ^$_
объединяет бесконечный список-2, -1, 0, 1, ...
со списком0, 1, ... $_-1
($_
являющимся аргументом функции), создавая список(-2, 0), (-1, 1), (0, 2), ..., ($_-3, $_-1)
. (Очевидно, что ни одно из этих чисел, меньших 3, не может быть в простой паре, но3..* Z 5..^$_
на несколько байтов длиннее, и ни одно из дополнительных чисел не является простым.)grep
выбирает только те пары , где все (то есть оба) числа являются простыми, иflat
сглаживает их в обычный список номеров.«/»
является гипероператором подразделения; со списком справа и1
слева он превращает список простых пар в их взаимные значения, которые затем суммируютсяsum
.источник
Clojure, 147 байтов
И Clojure приходит мертвым последним, как обычно.
Ungolfed:
источник
Юлия 0,4 ,
4846 байтПопробуйте онлайн!
источник
Утилиты Bash + GNU,
8685 байтПопробуйте онлайн!
Создает большое арифметическое выражение и затем передает его для
bc -l
его оценки.Редактировать: по ошибке оставили в паре $ (...) из старой версии с вложенной подстановкой команд; изменил на backticks, чтобы сохранить байт.
источник
APL NARS, 216 байтов, 108 символов
это будет использовать "Crivello di Eratostene" для поиска подсписка в 1..arg простых чисел запроса. Тест:
источник