Sequentially Divisible

Question

Sometimes to fall asleep, I'll count as high as I can, whilst skipping numbers that are not square-free. I get a little thrill when I get to skip over several numbers in a row - for example, 48,49,50 are all NOT square-free (48 is divisible by 2^2, 49 by 7^2, and 50 by 5^2).

This led me to wondering about the earliest example of adjacent numbers divisible by some arbitrary sequence of divisors.

Input

Input is an ordered list a = [a_0, a_1, ...] of strictly positive integers containing at least 1 element.

Output

Output is the smallest positive integer n with the property that a_0 divides n, a_1 divides n+1, and more generally a_k divides n+k. If no such n exists, the function/program's behavior is not defined.

Test Cases

[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

Scoring

This is code-golf; shortest result (per language) wins bragging rights. The usual loopholes are excluded.

Answer 1

Wolfram Language (Mathematica), 51 bytes

Mod[ChineseRemainder[1-Range@Length@#,#],LCM@@#,1]&

Try it online!

Answer 2

Husk, 7 bytes

VδΛ¦⁰ṫN

Try it online!

Explanation

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.

Answer 3

MATL, 11 bytes

`Gf@q+G\a}@

Try it online!

`           % 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.

Not exactly optimized for speed... the largest testcase takes a full minute using MATL, and approximately 0.03s on MATLAB. There is a small possibility MATL has a bit more overhead.

Answer 4

JavaScript, 42 40 bytes

Will throw a recursion error if there is no solution (or the solution is too big).

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

Saved 2 bytes with a pointer from Rick Hitchcock

---

Try it

Enter a comma separated list of numbers.

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>

Answer 5

Python 3, 62 bytes

f=lambda x,n=1:all(j%k<1for j,k in enumerate(x,n))or-~f(x,n+1)

Try it online!

Answer 6

05AB1E, 9 bytes

Xµā<N+sÖP

Try it online!

Explanation

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

Answer 7

Haskell, 45 44 bytes

f a=[n|n<-[1..],1>sum(zipWith mod[n..]a)]!!0

Try it online!

Edit: -1 byte thanks to nimi!

Answer 8

Clean, 61 bytes

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

Try it online!

Answer 9

Pyth, 11 bytes

f!s.e%+kTbQ 

Try it online!

---

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

Answer 10

J, 23 bytes

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

Try it online!

Answer 11

R, 51 bytes

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

Try it online!

The use of any throws k warnings about implicit conversion to logical, where k is the return value.

Answer 12

Perl 6, 34 bytes

->\a{first {all ($_..*)Z%%a},^∞}

Try it online!

Answer 13

APL (Dyalog Unicode), 24 23 22 bytes

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

Try it online!

Technically, this is a tacit function. I had to make it so since the only input allowed is the list of integers. Uses ⎕IO←0 (0-indexing)

It's worth noting that the function times out if n doesn't exist.

Thanks to @ngn and @H.PWiz for 1 byte each.

How?

{∨/×⍺|⍵+⍳≢⍺:⍺∇⍵+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 ⍵.

Answer 14

Perl 5, 49 + 2 (-pa) = 51 bytes

$i=!++$\;($\+$i)%$_&&last,$i++for@F;$i<@F&&redo}{

Try it online!

Answer 15

Japt, 10 bytes

Will eventually output undefined if no solution exists, if it doesn't crash your browser first.

@e_X°vZÃ}a

Try it

---

Explanation

               :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?

Answer 16

Ruby, 48 bytes

->l{1+(1..1/0.0).find{|x|l.all?{|y|(x+=1)%y<1}}}

Try it online!

Answer 17

Python 2, 80 bytes

def f(l,n=1):
 while n:
	n+=1
	if all((n+i)%v<1for i,v in enumerate(l)):return n

Try it online!

Answer 18

Standard ML (MLton), 96 bytes

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

Try it online!

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

Try it online! Starting with n=1, the function f increments n until the all-condition is fulfilled, in which case n is returned.

tabulate(m,g) with some integer m and function g builds the list [g 0, g 1, ..., g m]. In our condition tabulate is called with the length of the input list l and a function which checks whether the ith element of l divides n+i. This yields a list of booleans, so all with the identity function fn x=>x checks whether all elements are true.

I found a nice golfing trick to shorten the identity function in this case by four bytes: Instead of the lambda (fn x=>x), the build-in function hd is used, which returns the first element of a list, and the resulting bools in tabulate are wrapped in [ and ] to create singleton lists.

Answer 19

PowerShell, 65 62 bytes

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

Try it online!

PowerShell doesn't have the equivalent of an any or some or the like, so we need a slightly different approach.

This takes input $args[0] as an array, then enters an infinite for loop. Each iteration we set $o to be 1 (explained later), and set $i to be ++$j. The incrementing $j keeps tabs on what the first number of the proposed solution is, while the $i will increment over the rest of the proposed solution.

We then send each element of the input $args[0] into a ForEach-Object loop. Inside the inner loop, we Boolean-multiply into $o the result of a calculation. This will make it so that if the calculation fails for a value, the $o will turn to 0. The calculation is !($i++%$_), or the Boolean-not of the modulo operation. Since any nonzero value is truthy in PowerShell, this turns any remainders into a falsey value, thus turning $o into 0.

Outside the inner loop, if $o is nonzero, we've found an incrementing solution that works, so we output $j and exit.

Answer 20

tinylisp, 108 bytes

(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

The last line is an unnamed lambda function that takes a list and returns an integer. Try it online!

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)))

Answer 21

Julia 0.6, 79 bytes

f(s,l=length(s),n=s[])=(while !all(mod.(collect(0:l-1).+n,s).==0);n+=s[];end;n)

Try it online!

Inputs without valid solutiosn will cause infinite looping... :)

Answer 22

Python 2, 78 bytes

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

EDIT: -26 thanks to @Chas Brown

Answer 23

Ruby, 47 46 43 42 bytes

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

Try it online!

NB: the (1..) syntax is only supported in ruby 2.6, for the moment TIO only supports 2.5 so the link is to an older version (43 bytes).

Answer 24

Jelly, 10 bytes

1Ḷ+$ọ¥Ạ¥1#

Try it online!

Answer 25

APL NARS, 140 bytes, 70 chars

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

test

  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

Answer 26

Java 8, 82 75 bytes

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

Explanation:

Try it online.

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