Как я могу сгенерировать простую последовательность Роуленда в J?

Question

Если вы не знакомы с последовательностью простых чисел Роуленда, вы можете узнать об этом здесь. Я создал уродливый процедурный монадический глагол в J, чтобы сгенерировать первые n членов в этой последовательности следующим образом:

rowland =: определение монады
    результат =. 0 $ 0
    т = 1 $ 7
    в то время как. (# результат) <у дел.
        а =. {: t
        п = 1 + # т
        т = t, a + n +. 
        д =. | - / _2 {. T
        если. d> 1 сделать.
            результат =. ~. результат, д
        конец.
    конец.
    результат)

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

Вот вывод rowland 20:

5 3 11 23 47 101 7 13 233 467 941 1889 3779 7559 15131 53 30323 60647 121403 242807

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

diffs =: monad: '}: (| @ - / @ (2 & {.), $: @}.) ^: (1 <#) y' 

Answer 1

У меня пока нет полного ответа, но в этом эссе Роджера Хуэя есть неявная конструкция, которую вы можете использовать для замены явных циклов while. Другой (связанный) путь - сделать внутреннюю логику блока неявным выражением, например:

FUNWITHTACIT =: ] , {: + {: +. 1 + #
rowland =: monad define
    result =. >a:
    t =. 7x
    while. (# result) < y do.
      t =. FUNWITHTACIT t
      d =.  | -/ _2 {. t
      result =. ~.result,((d>1)#d)
    end.
    result
)

(Возможно, вы захотите сохранить блок if для эффективности, так как я написал код таким образом, чтобы result изменяется независимо от того, было ли выполнено условие - если оно не было, изменение не имеет никакого эффекта. if логику можно даже записать обратно в молчаливое выражение с помощью оператора Agenda.)

Полное решение будет состоять в том, чтобы выяснить, как представить всю логику внутри цикла while как одну функцию, а затем использовать трюк Роджера для реализации логики while в качестве неявного выражения. Я посмотрю, что у меня получится.

Кроме того, я получил J, чтобы построить FUNWITHTACIT для меня, взяв первые несколько строк вашего кода, вручную подставив в функции, которые вы объявили, значения переменных (что я мог сделать, потому что все они по-разному работали с одним аргументом), заменил каждый экземпляр t с y и сказал J построить молчаливый эквивалент полученного выражения:

]FUNWITHTACIT =: 13 : 'y,({:y)+(1+#y)+.({:y)'
   ] , {: + {: +. 1 + #

Использование 13 для объявления монады - это то, как J знает, как взять монаду (иначе явно объявлено с 3 : 0, или же monad define как вы написали в своей программе) и преобразуйте явное выражение в неявное выражение.

РЕДАКТИРОВАТЬ:

Вот функции, которые я написал для avenue (2), которые я упомянул в комментарии:

candfun =: 3 : '(] , {: + {: +. 1 + #)^:(y) 7'
firstdiff =: [: | 2 -/\ ]
triage =: [: /:~ [: ~. 1&~: # ]
rowland2 =: triage @firstdiff @candfun

Эта функция генерирует первые n-много номеров кандидатов, используя отношение повторяемости Роуленда, оценивает их первые различия, отбрасывает все первые различия, равные 1, отбрасывает все дубликаты и сортирует их в порядке возрастания. Я не думаю, что это пока полностью удовлетворительно, поскольку аргумент устанавливает количество кандидатов, которые нужно попробовать, а не количество результатов. Но это все еще прогресс.

Пример:

   rowland2 1000
3 5 7 11 13 23 47 101 233 467 941

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

NB. rowrec takes y=(n,an) where n is the index and a(n) is the
NB. nth member of the rowland candidate sequence. The base case
NB. is rowrec 1 7. The output is (n+1,a(n+1)).
rowrec =: (1 + {.) , }. + [: +./ 1 0 + ]

rowland3 =: 3 : 0
 result =. >a:
 t =. 1 7
 while. y > #result do.
  ts =. (<"1)2 2 $ t,rowrec t
  fdiff =. |2-/\,>(}.&.>) ts
  if. 1~:fdiff do.
   result =. ~. result,fdiff
  end.
  t =. ,>}.ts
 end.
 /:~ result
) 

который находит первые y-много различных простых чисел Роуленда и представляет их в порядке возрастания:

   rowland3 20
3 5 7 11 13 23 47 53 101 233 467 941 1889 3779 7559 15131 30323 60647 121403 242807

Большая часть сложности этой функции связана с тем, что я работаю с массивами в штучной упаковке. Это не красивый код, но он только сохраняет 4+#result много элементов данных (которые растут в масштабе журнала) в памяти во время вычислений. Оригинальная функция rowland держит (#t)+(#result) элементы в памяти (которая растет в линейном масштабе). rowland2 y строит массив y-много элементов, что делает его профиль памяти почти таким же, как rowland даже если он никогда не выходит за пределы указанной границы. мне нравится rowland2 за его компактность, но без формулы, чтобы предсказать точный размер y необходимо создать n-много различных простых чисел, эту задачу нужно будет выполнить методом проб и ошибок и, таким образом, потенциально использовать гораздо больше циклов, чем rowland или же rowland3 на избыточные расчеты. rowland3 вероятно, более эффективен, чем моя версия rowland, поскольку FUNWITHTACIT пересчитывает #t на каждой итерации цикла - rowland3 просто увеличивает счетчик, который требует меньше вычислительных ресурсов.

Тем не менее, я не доволен rowland3Явные управляющие структуры. Кажется, должен быть способ выполнить это поведение, используя рекурсию или что-то в этом роде.

Answer 2

Хотя я уже отметил правильный ответ Эстанфорда, я проделал долгий и долгий путь с J, так как я задал этот вопрос. Вот гораздо более идиоматический способ генерации простой последовательности Rowland в J:

~. (#~ 1&<) | 2 -/\ (, ({: + ({: +. >:@#)))^:(1000 - #) 7

Выражение (, ({: + ({: +. >:@#)))^:(1000 - #) 7 генерирует так называемую оригинальную последовательность до 1000 членов. Первые отличия этой последовательности могут быть получены | 2 -/\абсолютные значения разностей каждых двух элементов. (Сравните это с моим оригинальным, многословным diffs глагол из оригинального вопроса.)

Наконец, мы удаляем единицы и дубликаты простых чисел ~. (#~ 1&<) чтобы получить последовательность простых чисел.

Это намного лучше, чем я делал это раньше. Его легко превратить в глагол n количество простых чисел с небольшой рекурсией.