Совместность и число пи

23

Введение

Теория чисел полна чудес в виде неожиданных связей. Вот один из них.

Два целых числа является со-премьером , если они не имеют общие моменты, кроме 1. Дан число N , рассмотрят все целые числа от 1 до N . Нарисуйте два таких целых числа случайным образом (все целые числа имеют одинаковую вероятность быть выбранными при каждом розыгрыше; розыгрыши являются независимыми и с заменой). Пусть p обозначает вероятность того, что два выбранных целых числа взаимно просты. Тогда p стремится к 6 / π 2 ≈ 0,6079 ... как N стремится к бесконечности.

Соревнование

Цель этой задачи состоит в вычислении р как функция от N .

В качестве примера рассмотрим N = 4. Есть 16 возможных пар, полученных из целых чисел 1,2,3,4. 11 из этих пар взаимно просты, а именно (1,1), (1,2), (1,3), (1,4), (2,1), (3,1), (4,1 ), (2,3), (3,2), (3,4), (4,3). Таким образом, р = 11/16 = 0,6875 для N = 4.

Точное значение р должно быть вычислено по меньшей мере , четырех знаков после запятой. Это подразумевает, что вычисления должны быть детерминированными (в отличие от Монте-Карло). Но это не должно быть прямым перечислением всех пар, как указано выше; любой метод может быть использован.

Можно использовать аргументы функции или stdin / stdout. Если отображается вывод, конечные нули могут быть опущены. Так, например, 0.6300может отображаться как 0.63. Он должен отображаться в виде десятичного числа, а не в виде дроби (отображение строки 63/100не допускается).

Критерий выигрыша - наименьшее количество байтов. Нет никаких ограничений на использование встроенных функций.

Контрольные примеры

Ввод / вывод (только четыре знака после запятой обязательны, как указано выше):

1    / 1.000000000000000
2    / 0.750000000000000
4    / 0.687500000000000
10   / 0.630000000000000
100  / 0.608700000000000
1000 / 0.608383000000000
Луис Мендо
источник
Есть ли границы диапазона входов?
Эрик Тауэрс
@EricTowers Программа должна работать для любого разумного размера, вплоть до ограничений памяти и типа данных. По крайней мере 1000
Луис Мендо
Разрешены ли рациональные числа как возвращаемые значения (не строки)? Мой язык имеет собственный рациональный тип, в котором 63/100допустимый литерал, пригодный для вычислений. (Langs, о котором я говорю: Factor , Racket )
кошка
@ Cat Конечно, давай! Примите во внимание требуемую точность, хотя
Луис Мендо

Ответы:

14

Желе , 12 8 байт

RÆṪSḤ’÷²

Попробуйте онлайн!

Следующий двоичный код работает с этой версией интерпретатора Jelly .

0000000: 52 91 b0 53 aa b7 9a 8a  R..S....

идея

Ясно, что количество пар (j, k) , для которых j ≤ k, а j и k взаимно просты, равно числу пар (k, j), которые удовлетворяют тем же условиям. Также, если j = k , j = 1 = k .

Таким образом, чтобы подсчитать количество пар простых чисел с координатами от 1 до n , достаточно вычислить количество m пар (j, k), такое что j ≤ k , а затем вычислить 2m - 1 .

Наконец, так как общая функция Эйлера φ (k) дает целые числа между 1 и k , которые взаимно просты с k , мы можем вычислить m как φ (1) +… + φ (n) .

Код

RÆṪSḤ’÷²    Input: n

R           Yield [1, ..., n].
 ÆṪ         Apply Euler's totient function to each k in [1, ..., n].
   S        Compute the sum of all results.
    Ḥ       Multiply the result by 2.
     ’      Subtract 1.
      ÷²    Divide the result by n².
Деннис
источник
2
О, желе включает в себя функцию totient !? Хорошая идея!
Луис Мендо
2
Обратный отсчет до MATL включает в себя тотальное командование в день Т-1 ...
Quintopia
@quintopia (я, наконец, включил функцию totient) :-D
Луис Мендо
14

Mathematica 43 42 байта

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

  • Какая часть точек единичной решетки имеет взаимно простые координаты?
  • Какую долю единичных решеточных точек можно увидеть из начала координат?

сетка


N@Mean[Mean/@Boole@Array[CoprimeQ,{#,#}]]&

Примеры

Конечные нули опущены.

N@Mean[Mean/@Boole@Array[CoprimeQ,{#,#}]]&/@Range@10

{1, 0,75, 0,777778, 0,6875, 0,76, 0,638889, 0,714286, 0,671875, 0,679012, 0,63}


тайминг

Время в секундах предшествует ответу.

N@Mean[Mean/@Boole@Array[CoprimeQ,{#,#}]]&[1000]// AbsoluteTiming

{0.605571, 0.608383}

DavidC
источник
6

Mathematica, 42 32 байта

Count[GCD~Array~{#,#},1,2]/#^2.&

Анонимная функция, использует простую грубую силу. Последний случай выполняется на моей машине примерно за .37 секунд. Объяснение:

                               &   A function taking N and returning
Count[               , , ]           the number of
                      1               ones
                                     in the
                        2             second
                                     level of
         ~Array~                      a matrix of
      GCD                              the greatest common denominators of
                {#,#}                 all 2-tuples in [1..N]
                          /         divided by
                           #          N
                            ^2.      squared.
LegionMammal978
источник
Можете ли вы опубликовать пример прогона и объяснения для тех из нас, у кого нет Mathematica?
Луис Мендо
2
Это объединяет наши представления: Count[Array[GCD,{#, #}],1,2]/#^2.& будь моим гостем.
DavidC
4

Дьялог АПЛ, 15 байт

(+/÷⍴)∘∊1=⍳∘.∨⍳

Довольно просто. Это монадический функциональный поезд. Йота - это числа от 1 до ввода, поэтому мы берем внешнее произведение по gcd, а затем подсчитываем пропорцию единиц.

lirtosiast
источник
3

Октава, 49 47 байт

Просто подсчитать gcdвсе пары и посчитать .

@(n)mean(mean(gcd(c=kron(ones(n,1),1:n),c')<2))

Продукт Kronecker потрясающий.

flawr
источник
kron! Отличная идея!
Луис Мендо
Сначала я использовал meshgrid, но потом заметил, что могу сделать то же самое с kroninline! (-> анонимная функция)
flawr
2

JavaScript (ES6), 88 байт

n=>eval(`p=0;for(i=n;i;i--)for(j=n;j;j--,p+=a)for(a=1,k=j;k>1;k--)a=i%k||j%k?a:0;p/n/n`)

объяснение

n=>
  eval(`                     // use eval to enable for loop without {} or return
    p=0;                     // p = number of pairs
    for(i=n;i;i--)           // i = 1 to n
      for(j=n;j;j--,p+=a)    // j = i to n, a will equal 1 if i and j are coprime, else 0
        for(a=1,k=j;k>1;k--) // for each number from 0 to j
          a=i%k||j%k?a:0;    // if i%k and j%k are both 0, this pair is not coprime
    p/n/n                    // return result (equivalent to p/(n*n))
  `)

Тест

Требуется некоторое время для больших ( >100) значений n.

user81655
источник
2

Серьезно, 15 байтов

,;ª)u1x`▒`MΣτD/

Шестнадцатеричный дамп:

2c3ba62975317860b1604de4e7442f

Попробуйте онлайн

Я не собираюсь объяснять это, поскольку он буквально использует тот же алгоритм, что и решение Денниса Желе (хотя я получил его независимо).

quintopia
источник
2

J, 19 17 байт

*:%~1-~5+/@p:|@i:

Использование:

   (*:%~1-~5+/@p:|@i:) 4
0.6875

Объяснение:

*:%~1-~5+/@p:|@i:
               i: [-n..n]
             |@   absolute value of each element ([n..1,0,1,..n])
       5+/@p:     sum of the totient function for each element
    1-~           decreased by one, giving the number of co-prime pairs
*:%~              divided by N^2

Решение Денниса дает хорошее объяснение, как мы можем использовать функцию totient.

Попробуйте это онлайн здесь.

randomra
источник
2

Mathematica, 35 байт

Реализует алгоритм @ Денниса.

(2`4Plus@@EulerPhi@Range[#]-1)/#^2&

Вычислите сумму коэффициента (фи-функцию Эйлера) в диапазоне от 1 до входного значения. Умножьте на число с плавающей запятой два (с точностью до четырех цифр) и вычтите одно. (Больше точности можно сохранить, используя вместо " 2" и "1`4 ".) Это общее количество пар взаимно простых чисел, поэтому разделите их на квадрат ввода, чтобы получить искомую дробь. Потому что два приблизительное число, так и результат.

Тестирование (с данными о времени в левом столбце, так как по крайней мере один из нас считает это интересным), с функцией, назначенной fтак, чтобы тестовая строка была легче читаемой.

f=(2`4Plus@@EulerPhi@Range[#]-1)/#^2&
RepeatedTiming[f[#]] & /@ {1, 2, 4, 10, 100, 1000}
(* {{5.71*10^-6, 1.000}, 
    {5.98*10^-6, 0.750}, 
    {0.000010  , 0.6875}, 
    {0.0000235 , 0.6300}, 
    {0.00028   , 0.6087}, 
    {0.0033    , 0.6084} }  *)

Редактировать: Показывать экстент диапазона входных данных (меняя точность на единицу вместо двух, потому что в противном случае результаты становятся довольно монотонными) и призывая других делать то же самое ...

f = (2 Plus @@ EulerPhi@Range[#] - 1`4)/#^2 &
{#}~Join~RepeatedTiming[f[#]] & /@ {1, 2, 4, 10, 100, 1000, 10^4, 10^5, 10^6, 10^7}
(*  Results are {input, wall time, output}
    {{       1,  5.3*10^-6, 1.000}, 
     {       2,  6.0*10^-6, 0.7500}, 
     {       4,  0.0000102, 0.68750}, 
     {      10,  0.000023 , 0.63000}, 
     {     100,  0.00028  , 0.6087000}, 
     {    1000,  0.0035   , 0.608383000}, 
     {   10000,  0.040    , 0.60794971000}, 
     {  100000,  0.438    , 0.6079301507000}, 
     { 1000000,  4.811    , 0.607927104783000}, 
     {10000000, 64.0      , 0.60792712854483000}}  *)

RepeatedTiming[]выполняет вычисления несколько раз и занимает среднее время, пытаясь игнорировать холодные кэши и другие эффекты, вызывающие выбросы времени. Асимптотический предел

N[6/Pi^2,30]
(*  0.607927101854026628663276779258  *)

поэтому для аргументов> 10 ^ 4 мы можем просто вернуть «0,6079» и соответствовать указанным требованиям к точности и точности.

Эрик Тауэрс
источник
2

Юлия, 95 байт

n->(c=combinations([1:n;1:n],2);((L=length)(collect(filter(x->gcd(x...)<2,c)))÷2+1)/L(∪(c)))

Просто прямой подход на данный момент; Я рассмотрю более короткие / более элегантные решения в ближайшее время. Это анонимная функция, которая принимает целое число и возвращает число с плавающей точкой. Чтобы вызвать его, присвойте его переменной.

Ungolfed:

function f(n::Integer)
    # Get all pairs of the integers from 1 to n
    c = combinations([1:n; 1:n], 2)

    # Get the coprime pairs
    p = filter(x -> gcd(x...) == 1, c)

    # Compute the probability
    return (length(collect(p)) ÷ 2 + 1) / length(unique(c))
end
Алекс А.
источник
Насколько я могу судить, вам не нужен collectленивый объект, чтобы взять его length.
кот
@cat Вы делаете для некоторых, где lengthне определен метод, как здесь для итератора отфильтрованных комбинаций. Точно так же endofне будет работать, потому что нет метода для этого типа getindex.
Алекс А.
@cat rangeне возвращает объект того же типа, что и combinations. Последний возвращает итератор для комбинаций, который является отдельным типом без определенного lengthметода. Смотрите здесь . (Также :синтаксис предпочтительнее rangeдля построения диапазонов;))
Алекс А.
2

Sage, 55 байтов

lambda a:n((sum(map(euler_phi,range(1,a+1)))*2-1)/a**2)

Благодаря тому, что Sage вычисляет все символически, проблемы с эпсилонами и числами с плавающей запятой не возникают. Компромисс заключается в том, чтобы следовать правилу выходного формата, необходим дополнительный вызов n()(функция десятичной аппроксимации).

Попробуйте онлайн

Mego
источник
Очень хорошо! Вы, кажется, используете Sage довольно часто в последнее время :-)
Луис Мендо,
@LuisMendo Sage великолепен и делает все. Это очень хорошо использовать для математических задач, потому что он имеет огромную встроенную библиотеку, такую ​​как Mathematica, но синтаксис лучше (в силу того, что a) не является Mathematica и b) построен на Python).
Mego
2

MATL , 20 17 байт

Это использует текущая версия (5.0.0) языка.

Подход, основанный на ответе @ flawr .

i:tg!X*t!Zd1=Y)Ym

Изменить (28 апреля 2015 г.) : попробуйте онлайн! После того, как этот ответ был опубликован, функцияY) была переименована в X: ; ссылка включает это изменение.

пример

>> matl i:tg!X*t!Zd1=Y)Ym
> 100
0.6087

объяснение

i:         % vector 1, 2, ... up to input number
tg!        % copy, convert into ones, transpose
X*         % Kronecker product. Produces a matrix
t!         % copy, transpose
Zd         % gcd of all pairs
1=         % is it equal to 1?
Y)         % linearize into column array
Ym         % compute mean

Старый ответ: 20 байт

Oi:t"t@Zd1=sb+w]n2^/

объяснение

O             % produce literal 0. Initiallizes count of co-prime pairs.
i             % input number, say N
:             % create vector 1, 2, ... N
t             % duplicate of vector
"             % for loop
    t         % duplicate of vector
    @         % loop variable: each element from vector
    Zd        % gcd of vector and loop variable. Produces a vector
    1=s       % number of "1" in result. Each "1" indicates co-primality
    b+w       % accumulate into count of co-prime pairs
]             % end
n2^/          % divide by N^2
Луис Мендо
источник
Не могли бы вы быть еще короче с подходом, подобным тому, который я использовал в октаве?
Flawr
Верно! Спасибо! На 3 байта меньше. Вы должны были сделать это самостоятельно в MATL :-)
Луис Мендо
Я бы попробовал, если бы не было времени до сна =)
flawr
1

PARI / GP , 25 байтов

Создание анонимной функции сэкономило бы байт, но тогда мне пришлось бы использовать selfего в целом , чтобы сделать его дороже.

f(n)=n^2-sum(j=2,n,f(n\j))
Чарльз
источник
1

фактор, 120 113 байтов

Я провел урок игры в гольф, и я не могу получить его короче.

Перевод: Юлия .

[ [a,b] dup append 2 <combinations> [ members ] keep [ first2 coprime? ] filter [ length ] bi@ 2 /i 1 + swap /f ]

Пример запускается на первых 5 тестовых примерах (значение 1000 заставляет его заморозить редактор, и я не могу быть обеспокоен компиляцией исполняемого файла прямо сейчас):

! with floating point division
IN: scratchpad auto-use {
      1    
      2    
      4    
      10   
      100  
    }
    [ 
      [1,b] dup append 2 <combinations> [ members ] keep 
      [ first2 coprime? ] filter [ length ] bi@ 2 /i 1 + swap /f 
    ]
    map

--- Data stack:
{ 1.0 0.75 0.6875 0.63 0.6087 }
! with rational division
IN: scratchpad auto-use {
      1    
      2    
      4    
      10   
      100  
    }
    [ 
      [1,b] dup append 2 <combinations> [ members ] keep 
      [ first2 coprime? ] filter [ length ] bi@ 2 /i 1 + swap / 
    ]
    map

--- Data stack:
{ 1.0 0.75 0.6875 0.63 0.6087 }
{ 1 3/4 11/16 63/100 6087/10000 }
Кот
источник
Добавить пример запуска может быть?
Луис Мендо
1
@ LuisMendo сделано!
кот
1

Самау , 12 байт

Отказ от ответственности: не участвует, потому что я обновил язык после того, как вопрос был опубликован.

▌;\φΣ2*($2^/

Шестнадцатеричный дамп (Samau использует кодировку CP737):

dd 3b 5c ad 91 32 2a 28 24 32 5e 2f

Используя тот же алгоритм, что и ответ Денниса в Jelly.

alephalpha
источник
0

Python2 / Pypy, 178 байт

xФайл:

N={1:set([1])}
n=0
c=1.0
e=input()
while n<e:
 n+=1
 for d in N[n]:
  m=n+d
  try:N[m].add(d)
  except:N[m]=set([d,m])
 for m in range(1,n):
  if N[m]&N[n]==N[1]:c+=2
print c/n/n

Бег:

$ pypy x <<<1
1.0
$ pypy x <<<10
0.63
$ pypy x <<<100
0.6087
$ pypy x <<<1000
0.608383

Код подсчитывает пары взаимно простых чисел (n,m) for m<nдважды ( c+=2). Это игнорирует, (i,i) for i=1..nчто в порядке, за исключением (1,1), таким образом, исправляется путем инициализации счетчика с 1( 1.0чтобы подготовиться к делению поплавка позже) для компенсации.


источник