24
\$\begingroup\$

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.

\$\endgroup\$

26 Answers 26

8
\$\begingroup\$

Wolfram Language (Mathematica), 51 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ ChineseRemainder[]? Wow. \$\endgroup\$ – FantaC Jan 24 '18 at 1:26
6
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ ah, I had n:q`QtG\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. \$\endgroup\$ – Giuseppe Jan 23 '18 at 13:25
  • 1
    \$\begingroup\$ @Giuseppe Too bad fq`QtG\a}@ returns an extraneous copy of the input. \$\endgroup\$ – Sanchises Jan 23 '18 at 13:29
5
\$\begingroup\$

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>

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

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!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Demolishes my 17 byte answer, ouch. \$\endgroup\$ – Magic Octopus Urn Jan 23 '18 at 19:52
3
\$\begingroup\$

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!

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

Clean, 61 bytes

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

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ I think you need [1..] instead of [0..] to avoid outputting 0, a non-positive integer, for singleton lists. \$\endgroup\$ – Laikoni Jan 23 '18 at 17:18
  • \$\begingroup\$ @Laikoni thanks, fixed. \$\endgroup\$ – Οurous Jan 23 '18 at 19:22
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Do you need the 2 at the end? I'm sure there's more to be saved here but I don't know Pyth. \$\endgroup\$ – Shaggy Jan 23 '18 at 9:37
  • \$\begingroup\$ @Shaggy and @Giuseppe, both of you are right, and dropping the ending 2 fixes the issue \$\endgroup\$ – Dave Jan 23 '18 at 12:07
2
\$\begingroup\$

J, 23 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Jonah Jan 26 '18 at 3:15
  • 1
    \$\begingroup\$ @Jonah - I don't know if it works always; just all the tests I did were in these limits. \$\endgroup\$ – Galen Ivanov Jan 26 '18 at 9:12
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 47 bytes! \$\endgroup\$ – plannapus Mar 21 '18 at 16:07
  • \$\begingroup\$ @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! \$\endgroup\$ – Giuseppe Mar 21 '18 at 16:30
  • \$\begingroup\$ arf indeed and then forcing seq_along is just too long. \$\endgroup\$ – plannapus Mar 21 '18 at 16:36
  • \$\begingroup\$ So, but using sum instead of any get rid of those warnings, FYI. \$\endgroup\$ – plannapus Mar 22 '18 at 8:42
2
\$\begingroup\$

Perl 6, 34 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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 ⍵.
\$\endgroup\$
1
\$\begingroup\$

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

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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?
\$\endgroup\$
1
\$\begingroup\$

Ruby, 48 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)))
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Nice! I turned your loop exit condition around, and your idea can be improved upon to get 78 bytes . \$\endgroup\$ – Chas Brown Mar 22 '18 at 7:40
  • \$\begingroup\$ @ChasBrown thanks, I didn't think of doing it that way. Changed! \$\endgroup\$ – sonrad10 Mar 22 '18 at 10:10
0
\$\begingroup\$

Jelly, 10 bytes

1Ḷ+$ọ¥Ạ¥1#

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.