Естественный основной генератор

42

Существует довольно большое количество простых производящих функций. Практически все они построены и основаны на сите Эратосфена, функции Мёбиуса или теореме Вильсона и, как правило, невозможно вычислить на практике. Но есть и генераторы, которые имеют очень простую структуру и были найдены случайно.

В 2003 году Стивен Вольфрам исследовал класс вложенных рекуррентных уравнений в эксперименте с живым компьютером в Летней школе NKS. Группа людей вокруг Мэтью Фрэнка провела дополнительные эксперименты и обнаружила интересное свойство просто повторения

a(n) = a(n-1) + gcd(n,a(n-1))

с начальным значением a(1) = 7. Разница a(n) - a(n-1) = gcd(n,a(n-1))всегда казалась 1 или простым. Первые несколько отличий ( OEIS A132199 ):

1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1, 
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3, ...

Если мы пропустим только 1, мы получим следующую последовательность ( OEIS A137613 ):

5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 
941, 3, 7, 1889, 3, 3779, 3, 7559, 3, 13, 15131, 3, 53, 3, 7, 30323, 3, ...

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

Поскольку этот простой генератор не был построен, а просто найден случайно, основной генератор называется «встречающимся в природе». Но обратите внимание, что на практике этот генератор также невозможно вычислить. Как оказалось, простое число p появляется только после (p–3)/2последовательных 1 с. Тем не менее, реализация этого простого генератора будет вашей задачей.

Вызов:

Напишите функцию или программу, которая печатает первые nэлементы последовательности A137613(последовательность без 1). Вы можете прочитать входной номер n >= 0через STDIN, аргумент командной строки, приглашение или аргумент функции. Выведите первые nэлементы в любом читаемом формате в STDOUT или верните массив или список с этими значениями.

Это код-гольф. Поэтому самый короткий код выигрывает.

Leaderboard:

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

# Language Name, N bytes

где N - размер вашей заявки. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Показать фрагмент кода

code-golf number sequence primes number-theory Jakube
источник
1
Хотя основной генератор не создан, вы эффективно реализуете пробное деление с помощью рекурсии.
orlp
Если a (1) = 7, почему последовательность не начинается с 7?
feersum
3
@feersum, потому что последовательность, с которой мы имеем дело,a(n)-a(n-1)
Maltysen
Может nбыть ноль?
Sp3000
1
@jrenk Не уверен. Возможно, посчитайте это как 2 байта (так как вы удаляете 2 символа //) и объясните это в своем представлении. Если кто-то не согласен с вами, вы всегда можете отредактировать свой пост.
Якуб

Ответы:

7

Python 3.5.0b1 +, 95 93 байта

Ссылка на Python 3.5.0b1 + релиз

import math
def f(k,n=2,a=7,L=[]):x=math.gcd(n,a);return k and f(k-1%x,n+1,a+x,L+1%x*[x])or L

Прямая реализация повторения, показывающая:

  • Наш хороший друг 1%xи
  • math.gcd, в отличие от fractions.gcd.
Sp3000
источник
Что делает 1%x? Дополнительный вопрос: где я могу найти документацию по истории изменений Python, которая включает в себя бета-версии? Изменить: Nevermind, нашел его в нижней части истории изменений .
mbomb007
@ mbomb007 С тех пор x >= 1, 1%xвозвращает 0, если x == 11, в противном случае (используется, чтобы решить, следует ли добавить xв список)
Sp3000
5

Юлия, 110 байт

n->(a(n)=(n≥1&&(n==1?7:a(n-1)+gcd(n,a(n-1))));i=2;j=0;while j<n x=a(i)-a(i-1);x>1&&(j+=1;println(x));i+=1end)

Ungolfed:

function a(n::Int)
    n ≥ 1 && (n == 1 ? 7 : a(n-1) + gcd(n, a(n-1)))
end

function f(n::Int)
    i = 2;
    j = 0;
    while j < n
        x = a(i) - a(i-1)
        if x > 1
            j += 1
            println(x)
        end
        i += 1
    end
end
Алекс А.
источник
Ух ты, идеальный 8к, хороший: D
Beta Decay
1
Используйте n<2вместо n==1. Кроме того, если вы смотрите вперед, а не назад, вы можете использовать i=1и x=a(i)-a(i+=1), а затем println(-x)и -x>1исправить негативность, тем самым избегая необходимости отдельного увеличения i. И ≥это три байта, а >=это два ... но тогда вы можете использовать, n<1||()а не n>=1&&()... и, тем не менее, это даже не нужно в первую очередь (отбросьте условное, n никогда не будет меньше 1). Вам также не нужны внешние скобки при определении (n). С этими изменениями вы должны как минимум сократить до 97 байт.
Глен О
5

PHP, 101 96 99 98 77 72 байта

<?for(;2>$t=gmp_strval(gmp_gcd(~++$i,7+$e+=$t))or$argv[1]-=print"$t ";);


Использование:
Вызовите скрипт с аргументом: php -d error_reporting=0 script.php 30
если вы хотите протестировать его, вам нужно раскомментировать ;extension=php_gmp.dllв вашем php.ini
-> extension=php_gmp.dll
Должен ли я добавить расширение к моему счетчику байтов? Есть предположения?


Лог:
Сохранено 3 байта благодаря Исмаилу Мигелю.
Сохранено 26 байтов благодаря primo.

jrenk
источник
1
Вы можете сократить свой начальный тег <?и удалить определение $j.
Исмаэль Мигель
1
Да, это имеет значение. Но вы можете удалить эту новую строку. Что сэкономит 1-2 байта, в зависимости от того, как вы посчитали размер вашего кода.
Исмаэль Мигель
1
Незначительные улучшения: Используйте <в $j<=$argv[1](печатает слишком много) (-1). Оставьте $eнеинициализированным, используйте $e+7вместо этого (-3). Используйте for(;;)вместо того while(), чтобы использовать пре- и пост-выражения (-2). Заменить echo$t.' ';$j++на $j+=print"$t ", опустить скобки (-3). Заменить if($t>1)на 2>$t||(-2). Объедините присвоение $tс условным, переключитесь ||на or, снимите скобки (-5). Перейти $argv[1]к $jприращению, переместить все выражение в forусловное (-2). Изменить >=$j+=printна -=print(-3). Шаг за шагом: codepad.org/s6LNSPSM
Primo
1
@Primo спасибо за хорошее объяснение! Не знал, что смогу сделать все это.
Джренк
1
Еще несколько: Объединить $e+7с $e+=$t(-2). Оставьте $iнеинициализированным, используйте ~++$iвместо этого (-3). codepad.org/fDIImajp
primo
4

Haskell, 51 байт

d=zipWith gcd[2..]$scanl(+)7d
f=($filter(>1)d).take

Обратите внимание, что fэто функция, которая будет возвращать первые n элементов.

Вместо того, чтобы вычислять a(n)и затем обрабатывать различия, мы вычисляем различия d(n)и суммируем их вместе, чтобы получить a(n). (Те, кто не знаком с Haskell, могут возразить, что a(n)сначала нам нужно получить их d(n), но, конечно, ленивая оценка помогает нам решить эту проблему!)

Ungolfed:

a = scanl (+) 7 d        -- yielding a(n) = 7 + d(1) + d(2) + ... + d(n-1)
d = zipWith gcd [2..] a  -- yielding d(n) = gcd(n+1, a(n))

f n = take n $ filter (> 1) d -- get rid of 1s and take the first n
Artelius
источник
4

Pyth, 30 байт

Очень плохо играется в гольф, может быть значительно уменьшена. Определяет рекурсивную функцию спереди, фильтрует .first-n, а затем отображает разницу.

L?tb+KytbibK7m-yhdyd.ft-yhZyZQ

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

Maltysen
источник
Это дает неправильный вывод дляn = 0
Sp3000
2
@ Sp3000, это ошибка в Pyth. Я вставлю запрос на получение.
Maltysen
Ошибка найдена и исправлена ​​- патч будет внедрен, когда github перестанет быть DDoS'ом.
Исаак
1
Вот оно: meta.codegolf.stackexchange.com/questions/5318/… . Лично я бы рассмотрел исправления ошибок в языках программирования в качестве ответа
Томас Уэллер
2
@ThomasWeller Это как бы достигло всего языка ...
isaacg
4

Юлия, 69 67 байт

n->(i=1;a=7;while n>0 x=gcd(i+=1,a);a+=x;x>1&&(n-=1;println(x))end)

Это простое итеративное решение проблемы. xэто разница (которая есть gcd), а затем я обновляю a, добавляя x.

Глен О
источник
Я думаю, что это печатает A231900 .
alephalpha
@alephalpha - я думаю, что вижу ошибку. Легко исправляется. Даже побрил два байта в процессе.
Глен O
3

JavaScript (ES6), 91

Рекурсивный gcd, итерационная основная функция. Не так быстро.

Обычное примечание: тестирование запуска сниппета в любом браузере, совместимом с EcmaScript 6 (особенно не Chrome и не MSIE. Я тестировал на Firefox, Safari 9 мог пойти) 

F=m=>{
  for(G=(a,b)=>b?G(b,a%b):a,o=[],p=7,n=1;m;d>1&&(o.push(d),--m))
    p+=d=G(++n,p);
  return o
}

O.innerHTML=F(+I.value)
<input id=I value=10><button onclick='O.innerHTML=F(+I.value)'>-></button>
<pre id=O></pre>
Развернуть фрагмент

edc65
источник
3

Haskell, 74 71 66 байт

f=($filter(>1)$tail>>=zipWith(-)$scanl(\x->(x+).gcd x)7[2..]).take

Использовал трюк здесь: https://codegolf.stackexchange.com/a/39730/43318 , и сделал бессмысленно.

(Предыдущий: 71 байт)

a=scanl(\x->(x+).gcd x)7[2..]
f m=take m$filter(>1)$zipWith(-)(tail a)a

Сначала сделайте последовательность а, а затем возьмите различия.

(Предыдущий: 74 байта)

f m=take m$filter(>1)$map snd$scanl(\(x,d)->(\y->(x+y,y)).gcd x)(7,1)[2..]

Стандартные функции списка, плюс умное использование лямбда-функции. Обратите внимание, что это на 1 байт короче, чем более очевидный

g m=take m$filter(>1)$map snd$scanl(\(x,d)n->(x+gcd x n,gcd x n))(7,1)[2..]

Если мы не будем считать импорт, я могу уменьшить его до 66.

import Data.List
h m=take m$filter(>1)$snd$mapAccumL(\x->(\y->(x+y,y)).gcd x)7[2..]
Холден Ли
источник
3

PARI / GP, 60 байтов

a(n)=a=7;i=1;while(n,if(1<d=gcd(i+=1,a),n-=1;print(d));a+=d)

Взятые более или менее прямо из определения a (n) - a (n-1) = gcd (n, a (n-1))

Выход для a(20):

5
3
11
3
23
3
47
3
5
3
101
3
7
11
3
13
233
3
467
3
Примо
источник
2

C ++, 193 182 180 172 байта

Спасибо @Jakube - сэкономил 8 байт на выходе. 

int g(int a,int b){return a==b?a:a>b?g(b,a-b):g(a,b-a);}void f(int *r,int n){int m=1,i=0,a=7,b;while(i<n){b=g(a,++m);if(b>1){r[i]=b;++i;}a+=b;}}int main(){int r[6];f(r,6);}
EvgeniyZh
источник
Вероятно, вы можете сохранить несколько байтов, определив функцию f, которая возвращает массив с результатами. Таким образом, вы можете удалить include, scanf и print.
Якуб
2

Mathematica, 59 байт

For[i=j=1;a=7,i<=#,,d=GCD[++j,a];If[d>1,Print@d;i++];a+=d]&
alephalpha
источник