Делится последовательно

24

Иногда, чтобы заснуть, я буду считать настолько высоко, насколько смогу, пропуская числа, которые не являются квадратными . Я получаю немного острых ощущений, когда пропускаю несколько чисел подряд - например, 48,49,50все они НЕ квадратичные (48 делится на 2 ^ 2, 49 на 7 ^ 2 и 50 на 5 ^ 2).

Это заставило меня задуматься о самом раннем примере смежных чисел, которые делятся на произвольную последовательность делителей.

вход

Ввод - это упорядоченный список a = [a_0, a_1, ...]строго положительных целых чисел, содержащий как минимум 1 элемент.

Выход

Выход - это наименьшее положительное целое число nсо свойством, которое a_0делит n, a_1делит n+1и, в общем, a_kделит n+k. Если такого не nсуществует, поведение функции / программы не определено.

Тестовые случаи

[15] -> 15
[3,4,5] -> 3
[5,4,3] -> 55
[2,3,5,7] -> 158
[4,9,25,49] -> 29348
[11,7,5,3,2] -> 1518

счет

Это код-гольф ; самый короткий результат (для каждого языка) выигрывает право хвастаться. Обычные лазейки исключены.

code-golf Час Браун
источник
Относящиеся .
алефальфа

Ответы:

6

Шелуха , 7 байт

VδΛ¦⁰ṫN

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

объяснение

VδΛ¦⁰ṫN  Input is a list x.
      N  The list [1,2,3...
     ṫ   Tails: [[1,2,3...],[2,3,4...],[3,4,5...]...
V        Index of first tail y satisfying this:
  Λ       Every element
    ⁰     of x
   ¦      divides
 δ        the corresponding element of y.
Zgarb
источник
5

MATL , 11 байт

`Gf@q+G\a}@

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

`           % Do ....
 Gf         %   Convert input to [1,2,...,]
   @q+      %   Add current iteration index minus one, to get [n, n+1, ....]
      G\    %   Elementwise mod([n,n+1,...],[a_0,a_1,...])
        a   % ...while any of the modular remainders is nonzero.
         }  % Finally:
          @ %   Output the iteration index.

Не совсем оптимизирован по скорости ... самый большой тестовый цикл занимает целую минуту с использованием MATL и примерно 0,03 с на MATLAB. Существует небольшая вероятность того, что у MATL немного больше накладных расходов.

Sanchises
источник
ах, у меня было n:q`QtG\a]1)12 байт, но n:, очевидно, так же, как fздесь. Я всегда об этом забываю, поэтому вы можете добавить его в качестве альтернативы 11 байтов.
Джузеппе
1
@Giuseppe Слишком плохо fq`QtG\a}@возвращает постороннюю копию ввода.
Санчизес
5

JavaScript, 42 40 байт

Выдает ошибку рекурсии, если нет решения (или решение слишком большое).

a=>(g=y=>a.some(x=>y++%x)?g(++n):n)(n=1)

Сохранено 2 байта с указателем от Рика Хичкока

Попытайся

Введите список номеров через запятую.

o.innerText=(f=
a=>(g=y=>a.some(x=>y++%x)?g(++n):n)(n=1)
)(i.value=[5,4,3]);oninput=_=>o.innerText=f(i.value.split`,`.map(eval))
<input id=i><pre id=o>
Развернуть фрагмент

мохнатый
источник
Хороший подход, но терпит неудачу при превышении пределов рекурсии, например, с [4,9,25,49].
Час Браун
1
@ChasBrown, для целей кода гольф, мы можем предполагать бесконечную память.
Лохматый
Я думаю, что это будет работать для 38 байтов: (a,y=n=0)=>a.some(x=>y++%x)?f(a,++n):n
Рик Хичкок
Отлично, @RickHitchcock - спасибо. Не забывайте f=, хотя.
Лохматый
Ах, конечно. Это 40 байтов.
Рик Хичкок
3

05AB1E , 9 байтов

Xµā<N+sÖP

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

объяснение

Xµ          # loop until counter equals 1
  ā         # push range [1 ... len(input)]
   <        # decrement
    N+      # add current iteration index N (starts at 1)
      sÖ    # elementwise evenly divisible by
        P   # product
            # if true, increase counter
            # output N
Emigna
источник
Сносит мой 17-байтовый ответ, ой.
Волшебная Урна Осьминога
3

Чисто , 61 байт

import StdEnv
$l=hd[n\\n<-[1..]|and[i/e*e==i\\i<-[n..]&e<-l]]

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

Οurous
источник
2
Я думаю, что вам нужно [1..]вместо того, [0..]чтобы избегать вывода 0неположительного целого числа для одноэлементных списков.
Лайкони
@ Лайкони спасибо, исправлено.
Οurous
3

Pyth , 11 байт

f!s.e%+kTbQ

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

f!s.e%+kTbQ         Full program - inputs list from stdin and outputs to stdout
f                   First number T such that
   .e     Q         The enumerated mapping over the Input Q
      +kT           by the function (elem_value+T)
     %   b          mod (elem_index)
 !s                 has a false sum, i.e. has all elements 0
Дейв
источник
Вам нужно 2в конце? Я уверен, что здесь можно сохранить еще кое-что, но я не знаю Пита.
Лохматый
@Shaggy и @Giuseppe, вы оба правы, и удаление финала 2решает проблему
Дэйв
2

J , 23 байта

[:I.0=]+/@:|"1#]\[:i.*/

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

Гален Иванов
источник
Ницца. Какой математический факт позволяет вам проверять только произведение входов? Откуда мы знаем, что не может быть решения помимо этого? Кроме того, как мы узнаем, I.вернется только 1 результат? Разве не возможно, что есть несколько?
Иона
1
@ Джона - я не знаю, работает ли это всегда; только все тесты, которые я сделал, были в этих пределах.
Гален Иванов
2

R , 51 байт

function(l){while(any((F+1:sum(l|1))%%l))F=F+1
F+1}

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

Использование anythrows kпредупреждений о неявном преобразовании в logical, где kэто возвращаемое значение.

Giuseppe
источник
47 байтов !
планнапус
@plannapus Я думал об этом, но, к сожалению, это не сработало l=c(15), потому seq(l)==1:lчто в этом случае. seqтак раздражает!
Джузеппе
Арф действительно, и тогда принуждение seq_alongслишком длинное.
plannapus
Таким образом, но sumвместо того, anyчтобы избавиться от этих предупреждений, к вашему сведению.
plannapus
2

APL (Dyalog Unicode) , 24 23 22 байта

{∨/×⍺|⍵+⍳⍴⍺:⍺∇⍵+1⋄⍵}∘1

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

Технически, это молчаливая функция. Я должен был сделать это так, поскольку единственный вход разрешен - это список целых чисел. Использует ⎕IO←0(0-индексация)

Стоит отметить, что функция отключается, если nее не существует.

Спасибо @ngn и @ H.PWiz за 1 байт каждый.

Как?

{∨/×⍺|⍵+⍳≢⍺:⍺∇⍵+1⋄⍵}∘1 ⍝ Main function. ⍺=input; ⍵=1.
{                   }∘1 ⍝ Using 1 as right argument and input as left argument:
           :            ⍝ If
        ⍳≢⍺             ⍝ The range [0..length(⍺)]
      ⍵+                ⍝ +⍵ (this generates the vector ⍵+0, ⍵+1,..., ⍵+length(⍺))
    ⍺|                  ⍝ Modulo ⍺
   ×                    ⍝ Signum; returns 1 for positive integers, ¯1 for negative and 0 for 0.
 ∨/                     ⍝ Logical OR reduction. Yields falsy iff the elements of the previous vector are all falsy.
            ⍺∇⍵+1       ⍝ Call the function recursively with ⍵+1.
                 ⋄⍵     ⍝ Else return ⍵.
Ж. Салле
источник
1

Japt, 10 байт

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

@e_X°vZÃ}a

Попытайся

объяснение

               :Implicit input of array U
@       }a     :Loop and output the first integer X that returns true.
 e_    Ã       :For every element Z in U
   X°          :X, postfix increcemnted
     vZ        :Is it divisible by Z?
мохнатый
источник
1

Стандартный ML (MLton) , 96 байт

open List;fun$n% =if all hd(tabulate(length%,fn i=>[1>(n+i)mod nth(%,i)]))then n else$(n+1)%;$1;

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

Ungolfed:

open List
fun f n l = 
    if all (fn x=>x)
           (tabulate ( length l
                     , fn i => (n+i) mod nth(l,i) = 0))
    then n 
    else f (n+1) l
val g = f 1

Попробуйте онлайн! Начиная с n=1, функция fувеличивается nдо тех пор, пока не allбудет выполнено условиеn возвращается.

tabulate(m,g)с некоторым целым числом mи функцией gстроит список [g 0, g 1, ..., g m]. В наших условиях tabulateвызывается длина входного списка lи функция, которая проверяет, делится ли iэлемент th . Это дает список логических значений, поэтому с помощью функции identity проверяется, являются ли все элементы истинными.ln+iallfn x=>x

Я нашел хороший гольф трюк , чтобы сократить тождественную функцию в этом случае четыре байта: Вместо лямбда (fn x=>x), сборка-функции hdиспользуются, которая возвращает первый элемент списка, и в результате Bools в tabulateобернут [и ]к создавать одиночные списки.

Laikoni
источник
1

PowerShell , 65 62 байта

for(){$o=1;$i=++$j;$args[0]|%{$o*=!($i++%$_)};if($o){$j;exit}}

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

PowerShell не имеет эквивалента anyили someподобного, поэтому нам нужен немного другой подход.

Это принимает входные данные $args[0]в виде массива, а затем входит в бесконечный forцикл. Каждую итерацию мы устанавливаем, $oчтобы быть 1(объясненный позже), и устанавливаем, $iчтобы быть ++$j. Инкремент $jсохраняет вкладки о том, что является первым номером предложенного решения, в то время как $iбудет увеличиваться по сравнению с остальной частью предложенного решения.

Затем мы отправляем каждый элемент ввода $args[0]в ForEach-Objectцикл. Внутри внутреннего цикла мы логически умножаем $oрезультат вычисления. Это сделает так, что если вычисление не удастся для значения,$o переключится на 0. Вычисление !($i++%$_), или Булево-нет операции по модулю. Поскольку любое значение, отличное от нуля, является правдивым в PowerShell, это превращает любые остатки в ложное значение, превращаясь, таким образом, $oв 0.

Вне внутреннего цикла, if $oотличного от нуля, мы нашли инкрементное решение, которое работает, поэтому мы выводим $jи exit.

AdmBorkBork
источник
1

тинилисп , 108 байт

(load library
(d ?(q((L N)(i L(i(mod N(h L))0(?(t L)(inc N)))1
(d S(q((L N)(i(? L N)N(S L(inc N
(q((L)(S L 1

Последняя строка - это безымянная лямбда-функция, которая принимает список и возвращает целое число. Попробуйте онлайн!

Ungolfed

(load library)

(comment Function to check a candidate n)
(def sequentially-divisible?
 (lambda (divisors start-num)
  (if divisors
   (if (divides? (head divisors) start-num)
    (sequentially-divisible? (tail divisors) (inc start-num))
    0)
   1)))

(comment Function to check successive candidates for n until one works)
(def search
 (lambda (divisors start-num)
  (if (sequentially-divisible? divisors start-num)
   start-num
   (search divisors (inc start-num)))))

(comment Solution function: search for candidates for n starting from 1)
(def f
 (lambda (divisors)
  (search divisors 1)))
DLosc
источник
1

Python 2, 78 байт

def f(a,c=0):
 while [j for i,j in enumerate(a) if(c+i)%j<1]!=a:c+=1
 return c

РЕДАКТИРОВАТЬ: -26 благодаря @Chas Brown

sonrad10
источник
Ницца! Я изменил ваше условие выхода из цикла, и ваша идея может быть улучшена, чтобы получить 78 байтов .
Час Браун
@ChasBrown спасибо, я не думал делать это таким образом. Измененный!
sonrad10
0

APL NARS, 140 байтов, 70 символов

r←f w;i;k
i←r←1⊃,w⋄k←¯1+⍴w⋄→0×⍳k=0
A:→0×⍳0=+/(1↓w)∣(k⍴r)+⍳k⋄r+←i⋄→A

тест

  f 15
15
  f 3 4 5
3
  f 5 4 3
55
  f 2 3 5 7
158
  f 4 9 25 49
29348
  f 11 7 5 3 2 
1518
RosLuP
источник
0

Java 8, 82 75 байт

a->{for(int r=1,i,f;;r++){i=f=0;for(int b:a)f+=(r+i++)%b;if(f<1)return r;}}

Объяснение:

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

a->{                 // Method with integer-array parameter and integer return-type
  for(int r=1,       //  Return-integer, starting at 1
          i,         //  Index-integer
          f;         //  Flag-integer
      ;r++){         //  Loop indefinitely, increasing `r` by 1 after every iteration
    i=f=0;           //   Reset both `i` and `f` to 0
    for(int b:a)     //   Inner loop over the input-array
      f+=(r+i++)%b;  //    Increase the flag-integer by `r+i` modulo the current item
    if(f<1)          //   If the flag-integer is still 0 at the end of the inner loop
      return r;}}    //    Return `r` as result
Кевин Круйссен
источник
0

Рубин , 47 46 43 42 байта

->a{(1..).find{|i|a.all?{|v|i%v<1&&i+=1}}}

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

Примечание: (1..)синтаксис поддерживается только в ruby ​​2.6, на данный момент TIO поддерживает только 2.5, поэтому ссылка на более старую версию (43 байта).

Асоне Тухид
источник