Sequentially Divisible

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
[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 ; shortest result (per language) wins bragging rights. The usual loopholes are excluded.

• Jan 23 '18 at 3:04

Wolfram Language (Mathematica), 51 bytes

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

Try it online!

• ChineseRemainder[]? Wow. Jan 24 '18 at 1:26

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.

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.

• ah, I had n:qQtG\a]1) for 12 bytes but n: is obviously the same as f here. I always forget about that, so you can add it as an alternative 11 byter. Jan 23 '18 at 13:25
• @Giuseppe Too bad fqQtG\a}@ returns an extraneous copy of the input. Jan 23 '18 at 13:29

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>

• Nice approach, but fails by exceeding recursion limits with, e.g., [4,9,25,49]. Jan 23 '18 at 8:51
• @ChasBrown, for the purposes of code golf, we may assume infinite memory. Jan 23 '18 at 9:17
• I think this will work for 38 bytes: (a,y=n=0)=>a.some(x=>y++%x)?f(a,++n):n Jan 23 '18 at 15:59
• Oo, nice one, @RickHitchcock - thanks. Don't forget the f=, though. Jan 23 '18 at 16:27
• Ah, of course. It's 40 bytes. Jan 23 '18 at 16:28

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!

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
• Demolishes my 17 byte answer, ouch. Jan 23 '18 at 19:52

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

Try it online!

Edit: -1 byte thanks to nimi!

• sum(zipWith mod[n..]a)<1.
– nimi
Jan 23 '18 at 15:25

import StdEnv
$l=hd[n\\n<-[1..]|and[i/e*e==i\\i<-[n..]&e<-l]] Try it online! • I think you need [1..] instead of [0..] to avoid outputting 0, a non-positive integer, for singleton lists. Jan 23 '18 at 17:18 • @Laikoni thanks, fixed. Jan 23 '18 at 19:22 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 • Do you need the 2 at the end? I'm sure there's more to be saved here but I don't know Pyth. Jan 23 '18 at 9:37 • @Shaggy and @Giuseppe, both of you are right, and dropping the ending 2 fixes the issue – Dave Jan 23 '18 at 12:07 J, 23 bytes [:I.0=]+/@:|"1#]\[:i.*/ Try it online! • Nice. What's the mathematical fact that allows you to only check up to the product of the inputs? How do we know there can't be a solution beyond that? Also, how do we know I. will only return 1 result? Isn't it possible there are multiple? Jan 26 '18 at 3:15 • @Jonah - I don't know if it works always; just all the tests I did were in these limits. Jan 26 '18 at 9:12 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. • Mar 21 '18 at 16:07 • @plannapus I considered that but it unfortunately fails for l=c(15), since seq(l)==1:l in that case. seq is annoying like that! Mar 21 '18 at 16:30 • arf indeed and then forcing seq_along is just too long. Mar 21 '18 at 16:36 • So, but using sum instead of any get rid of those warnings, FYI. Mar 22 '18 at 8:42 Perl 6, 34 bytes ->\a{first {all ($_..*)Z%%a},^∞}

Try it online!

• 30 bytes
– Jo King
Jan 23 '19 at 0:15

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 ⍵.

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

$i=!++$\;($\+$i)%$_&&last,$i++for@F;$i<@F&&redo}{ Try it online! 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? Ruby, 48 bytes ->l{1+(1..1/0.0).find{|x|l.all?{|y|(x+=1)%y<1}}} Try it online! 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! 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.

Try it online!

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

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

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