# 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] -> 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.

• – alephalpha Jan 23 '18 at 3:04

# Wolfram Language (Mathematica), 51 bytes

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


Try it online!

• ChineseRemainder[]? Wow. – RaviRavioli 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. – Giuseppe Jan 23 '18 at 13:25
• @Giuseppe Too bad fqQtG\a}@ returns an extraneous copy of the input. – Sanchises 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]. – Chas Brown Jan 23 '18 at 8:51
• @ChasBrown, for the purposes of code golf, we may assume infinite memory. – Shaggy 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 – Rick Hitchcock Jan 23 '18 at 15:59
• Oo, nice one, @RickHitchcock - thanks. Don't forget the f=, though. – Shaggy Jan 23 '18 at 16:27
• Ah, of course. It's 40 bytes. – Rick Hitchcock 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. – Magic Octopus Urn 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

# Clean, 61 bytes

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. – Laikoni Jan 23 '18 at 17:18 • @Laikoni thanks, fixed. – Οurous 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. – Shaggy 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? – Jonah 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. – Galen Ivanov 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. • – plannapus 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! – Giuseppe Mar 21 '18 at 16:30 • arf indeed and then forcing seq_along is just too long. – plannapus Mar 21 '18 at 16:36 • So, but using sum instead of any get rid of those warnings, FYI. – plannapus Mar 22 '18 at 8:42 # Perl 6, 34 bytes ->\a{first {all ($_..*)Z%%a},^∞}


Try it online!

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

# 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. # 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)))  # 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... :) # 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 • Nice! I turned your loop exit condition around, and your idea can be improved upon to get 78 bytes . – Chas Brown Mar 22 '18 at 7:40 • @ChasBrown thanks, I didn't think of doing it that way. Changed! – sonrad10 Mar 22 '18 at 10:10 # Jelly, 10 bytes 1Ḷ+$ọ¥Ạ¥1#


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