19
\$\begingroup\$

Given an infinite arithmetically-progressive¹ sequence, compute the minimum length of a prefix with a product divisible by 2^8.

Sample cases & reference implementation

Here is a reference implementation that I wrote in Io.

  1, 1 -> 10
  2, 4 -> 8
  3, 5 -> 10
  2, 6 -> 5
  7, 5 -> 6
  4, 1 -> 9
 10, 9 -> 7
256, 9 -> 1

Spec

  • The input will always be provided in a way such that it won't take forever to zero the accumulator.
  • ¹ An arithmetically progressive infinite list can be generated by a constant step each time starting from an initial number.
    • For the infinite list input, you're are allowed to simply take the initial number and the step of the infinite list.
  • There are only going to be integers in this sequence.

    Examples

  • 1*2*3*4*5*6*7*8*9*10 = 3,628,800 = 14,175*256

  • 2*6*10*14*18*22*26*30 = 518,918,400 = 2,027,025 * 256
\$\endgroup\$
1
  • 8
    \$\begingroup\$ Could you add a full explanation / solution process for one of the examples? \$\endgroup\$ May 30 '20 at 18:48

23 Answers 23

9
\$\begingroup\$

Python 2, 39 bytes

f=lambda a,d,p=1:p%256and-~f(a+d,d,p*a)

Try it online!

Tracks the product p of the arithmetic progression until it's divisible by 256.

\$\endgroup\$
6
  • \$\begingroup\$ I'm not sure, but i think the rules say that you can drop the f= part in front of a lambda \$\endgroup\$
    – Dion
    May 30 '20 at 5:37
  • \$\begingroup\$ like this \$\endgroup\$
    – Dion
    May 30 '20 at 5:43
  • 8
    \$\begingroup\$ @Dion Not if the function is recursive, since it needs to be assigned to refer to itself \$\endgroup\$
    – Jo King
    May 30 '20 at 6:54
  • \$\begingroup\$ @JoKing not dropped entierly, but just out of the byte count, see my tio \$\endgroup\$
    – Dion
    May 30 '20 at 6:58
  • 1
    \$\begingroup\$ @Dion It needs to work whatever name the header uses to refer to the lambda, so because it relies on a particular name then that needs to be included in the byte count. \$\endgroup\$
    – Neil
    May 30 '20 at 8:18
6
\$\begingroup\$

APL (Dyalog), 24 bytes

{0=256|×/⍵:≢⍵⋄⍺∇⍵,⍨⊃⍺+⍵}

Try it online!

is the the sequence (starting with the first item), the step.


0=256|×/⍵ - if the product is divisible by 256, ≢⍵ return the length.

⍺∇⍵ - else, recurse, ,⍨⊃⍺+⍵ - and append a new term to the sequence.

\$\endgroup\$
1
  • \$\begingroup\$ 23 bytes by using × instead of 0= (and swapping the two guards) \$\endgroup\$
    – rues
    Dec 4 '20 at 18:22
5
\$\begingroup\$

Husk, 9 bytes

V¦256G*¡+

Try it online! Takes first the step, then the initial value.

Explanation

V¦256G*¡+  Implicit arguments: step and start
        +  Function that adds step.
       ¡   Iterate on start to form infinite list [start, start+step, start+2*step..]
     G     Cumulative reduce by
      *    multiplication.
V          1-based index of first value that
 ¦256      is divisible by 256.
\$\endgroup\$
5
\$\begingroup\$

Raku, 38 31 bytes

{+($^a,*+$^b...{[*](@_)%%256})}

Try it online!

Does pretty much exactly what the description asks for. Generates the arithmetic sequence until the product of elements is divisible by 256 and returns the length of the list.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 33 bytes

Takes input as (step)(init).

s=>g=(i,p=1)=>p&&g(i+s,p*i%256)+1

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Wouldn't p%256 work better for products above 2**31? \$\endgroup\$
    – Neil
    May 30 '20 at 21:43
  • \$\begingroup\$ @Neil True. I seems also more sensible to put the modulo in the call so that the function doesn't return a false result when it really should loop forever -- such as for f(2)(1) -- even if it's guaranteed not to happen. \$\endgroup\$
    – Arnauld
    May 30 '20 at 23:31
5
\$\begingroup\$

INTERCAL, 471 445 443 bytes

I could have done anything else but I've always wanted to try this language out...

DOWRITEIN:5DOWRITEIN:6DO:8<-:5DO:7<-#1PLEASECOMEFROM(9)DO:1<-:6DO:2<-:7DO(1549)NEXTDO:1<-:3DO:2<-:5DO(1509)NEXTDO:1<-:3DO:2<-:8PLEASEDO(1549)NEXTDO:8<-:3DO:1<-:8DO:2<-#256PLEASEDO(1550)NEXTDO:4<-:1DO:1<-:3PLEASEDO(1540)NEXTDO:1<-:4DO:2<-:3PLEASEDO(1510)NEXTDO:1<-:3DO:2<-:3PLEASEDO(1550)NEXTDO:1<-#1DO:2<-:3DO(1509)NEXTDO(1)NEXTDO:1<-:7DO:2<-#1DO(1509)NEXT(9)DO:7<-:3(1)DO(2)NEXTPLEASEFORGET#1DO:1<-:7DO:2<-#1DO(1509)NEXTDO:7<-:3PLEASEREADOUT:7PLEASEGIVEUP(2)DORESUME:3

Inspired by Noodle9's C answer.

Formatted version: Try it online!

Explaination based on blocks, blocks seperated by double line breaks.
(if magic) marks code for an If-structure I've found in the manual.

Setup vars and input
 - :5 = start value
 - :6 = step size
 - :7 = step count
 - :8 = current cumultative product 

Label (99)

:8 *= (:7 * :6) + :5

Calculate :8 % 256 

Divide result by itself and add one.
If the result is 0, the division subroutine returns 0, else it returns 1.
We need to add one becase label (0) is invalid.

Store result in :10

Increment :7, store result in :3

(if magic)
If :10 is 2, put :3 in :7 and jump to (99)
(if magic)
If :10 is 1, print :3 and terminate
(if magic)

If someone can get rid of that double addition, I'd be very grateful.

EDIT

Found out a way to get rid of it. Also updated the explaination and fixed some formatting.

-2 by using a shorter label

\$\endgroup\$
4
\$\begingroup\$

MATL, 17 bytes

ha`&G@q*+*8W\t}x@

Try it online! Or verify all test cases.

Explanation

This uses the fact that mod(a*b, N) equals mod(mod(a, N)*b, N).

h       % Take the two inputs (implicitly): a (initial term), s (step).
        % Concatenate them into a row vector
a       % Any: true (or 1) if there is any nonzero entry. Gives true
`       % Do...while
  &G    %   Push the two inputs again: a, s
  @q    %   Push n-1, where n is the 1-based iteration index
  *     %   Multiply: gives s*(n-1)
  +     %   Add: gives a+s(n-1), which is the n-th term of the sequence
  *     %   Multiply this by the previous result (which was initialized to 1)
  8W    %   Push 8, exponential with base 2: gives 256
  \     %   Modulus
  t     %   Duplicate. This will be used as loop exit condition
}       % Finally (execute this on loop exit)
  x     %   Delete latest result (which is necessarily 0)
  @     %   Push current n. This is the solution
        % End (implicitly). A new iteration is executed if the top of the
        % stack is nonzero
        % Display (implicitly)
\$\endgroup\$
4
\$\begingroup\$

J, 30 29 bytes

[:#(],(+{:))^:(0<256|*/@])^:_

Try it online!

-1 byte thanks to Traws

Straightforward conversion of the algorithm into J.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ -1 byte with a: -> _ \$\endgroup\$
    – Traws
    May 30 '20 at 16:33
4
\$\begingroup\$

brainfuck, 80 71 bytes

,>>,->+[<[-<+>>[->+>+<<]>[-<+>]<<]<[->+<]<[->+>+<<]>[-<+>]>>>>[-<<+>>]>+<<<]>>>.

Try it online!

Takes two byte values as input (step, initial), output a byte value.

Commented code (Memory layout: count step init init' prod prod' prod'')

This language has a slight advantage for this challenge because its cell size value (in the TIO implementation) is 8-bit.

This program has to use ~5 variables, so some other rearrangement might produce a shorter program.

Use a scrolling tape to reduce back-and-forth copying. (after each iteration of the outermost loop the pointer is moved 1 unit to the right)

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

K (ngn/k), 27 25 19 18 bytes

-2 bytes thanks to Traws!

-6 bytes thanks to ngn and Traws!

-1 more byte thanks to ngn!

{#(`c$*/)(x,y+)/x}

Try it online!

\$\endgroup\$
11
  • 2
    \$\begingroup\$ -2 bytes with {#(256!*/){y,x+*|y}[y]/x} \$\endgroup\$
    – Traws
    May 30 '20 at 16:25
  • 1
    \$\begingroup\$ Yes, it uses projection/currying to avoid having to set a global. For example, +[2;3] can be computed as the projection +[2]3. \$\endgroup\$
    – Traws
    May 30 '20 at 18:35
  • 1
    \$\begingroup\$ @Traws Thank you, I learned something new today :) \$\endgroup\$ May 30 '20 at 19:07
  • 1
    \$\begingroup\$ @GalenIvanov @Traws you can also make projections/compositions by omitting the rightmost argument: {y,x+*|y}[y] -> (y,(*|y)+) \$\endgroup\$
    – ngn
    May 31 '20 at 21:17
  • 2
    \$\begingroup\$ @ngn Nice! I guess in this case it can all be further simplified to {#(256!*/)(x,y+)/x}. \$\endgroup\$
    – Traws
    Jun 1 '20 at 1:43
2
\$\begingroup\$

Factor, 105 bytes

: f ( n n -- n ) swap 1array
[ dup product 256 mod 0 = ]
[ 2dup last + 1array append ] until
length nip ;

Try it online!

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

APL (Dyalog), 19 bytes

{0⍳⍨256|×\⍵+⍺×0,⍳9}

Try it online!

Uses ⎕IO←1 and the fact that the highest possible output is 10.

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

Retina 0.8.2, 70 bytes

\d+
$*
^
1,
{`^1.*
$&#
\G1(?=1*,(1+))
$1
1{256}

}`1,(1+(,1+))
1$2$1
#

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

^
1,

Insert an accumulator.

^1.*
$&#

Increment the result if the accumulator is not zero.

\G1(?=1*,(1+))
$1

Multiply the accumulator by the current term.

1{256}

Reduce modulo 256.

1,(1+(,1+))
1$2$1

If the accumulator is not zero then calculate the next term. (The conditional is necessary in order for the loop to terminate once the accumulator reaches zero.)

{`
}`

Repeat the loop until the buffer stops changing. This will happen when the accumulator becomes zero, i.e. the product is a multiple of 256.

#

Convert the result to decimal.

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

Charcoal, 24 bytes

⊞υNNηW﹪ΠEυΣ…υ⊕λ²⁵⁶⊞υηILυ

Try it online! Link is to verbose version of code. Explanation:

⊞υN

Input the initial number and push it to the predefined empty list.

Nη

Input the step.

W﹪ΠEυΣ…υ⊕λ²⁵⁶

Repeat while the product of the sums of all the nontrivial prefixes of the list is not a multiple of 256...

⊞υη

... push the step to the list.

ILυ

Output the length of the list.

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

Brachylog, 23 bytes

≜;.{|⟨+≡t⟩ⁱ}ᶠ⁽hᵐ×%₂₅₆0∧

Try it online!

This took embarrassingly long to write, but at least I was able to shave two bytes off ∧.≜&{|⟨+≡t⟩ⁱ}ᶠ↖.hᵐ×%₂₅₆0∧ once I got that far. Takes [first term, step] through the output variable and outputs the prefix length through the input variable.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'm interested in knowing why this was downvoted. \$\endgroup\$ Jun 1 '20 at 21:03
  • 1
    \$\begingroup\$ Seems like someone went and downvoted all answers in golfing languages. \$\endgroup\$
    – Zgarb
    Jun 2 '20 at 8:05
1
\$\begingroup\$

Jelly, 16 bytes

1µ⁴ẋ³1¦ÄP256ḍµ1#

A full program accepting the initial value and the delta which prints the result.

Try it online!

How?

1µ⁴ẋ³1¦ÄP256ḍµ1# - Main Link: initial, delta
1                - set the left value (say n) to 1
              1# - increment n finding the first 1 such n which is truthy under:
 µ           µ   -   the monadic chain - i.e. f(n):
  ⁴              -     program argument 4 (delta)
   ẋ             -     repeated (n) times
      ¦          -     sparse application...
     1           -     ...to indices: 1
    ³            -     ...what: program argument 3 (initial)
       Ä         -     cumulative sums
        P        -     product
         256     -     literal 256
            ḍ    -     divides (the product)?
                 - implicit print (a list with a single element prints that element)
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 46 44 bytes

Saved 2 bytes thanks to Arnauld!!!

c;f(a,d){c=0;for(char p=1;p*=a+d*c++;);d=c;}

Try it online!

Commented code

c;f(a,d){
 c=0;           /* initialise counter */
 for(char p=1   /* initialise 8-bit product */
   p            /* loop until last 8-bits of product are 0 */
    *=a+d*      /* and multiply product by next element in series */
       c++;);   /* and bump counter */
 d=c;           /* return counter */
}
\$\endgroup\$
4
  • \$\begingroup\$ 44 bytes \$\endgroup\$
    – Arnauld
    May 30 '20 at 23:52
  • \$\begingroup\$ @Arnauld Nice one - thanks! :D \$\endgroup\$
    – Noodle9
    May 31 '20 at 8:11
  • \$\begingroup\$ To be pedantic, this only works with -fwrapv or -O0. -O3 breaks the program (char overflow is undefined behavior) \$\endgroup\$
    – DELETE_ME
    Jun 1 '20 at 15:31
  • \$\begingroup\$ Alternative 44: tio.run/##fZDbaoQwEIbv9ykGQYg6Ug/… (related ) \$\endgroup\$
    – DELETE_ME
    Jun 1 '20 at 15:34
1
\$\begingroup\$

Wolfram Language (Mathematica), 59 bytes

(t=0;s=#;k=#2;While[Mod[s##&@@Array[s+k#&,t++],256]!=0];t)&

Try it online!

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

R, 43 bytes

function(i,s)match(0,cumprod(i+0:9*s)%%256)

Try it online!

Outputs 'NA' if sequence goes to infinity without ever being a multiple of 256.

Calculates products of sequences up to length 10. Why is this enough?

If step is an odd number, then the successive factors that make up each element of the sequence will alternate between odd and even, so 10 would be enough to ensure that there are 5 even numbers multiplied together (so the product is a multiple of 2^5). But, the first 5 even numbers are also certain to include at least one multiple-of-4 (every second even number) and one multiple-of-8 (every fourth even number), so in fact their product is certain to be a multiple of 2^8 = 256.

If the step is even and the initial number is even, then (for similar reasons) only a maximum of 4 steps are needed.

If the step is even and the initial number is odd, then all the factors will be odd, so the product will always be odd and the sequence will go to infinity without ever being a multiple of 256.

So, if we didn't find a multiple-of-256 by the 10th element of the sequence, there won't be one, and we can just output the 'infinity' response.

I think.

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

05AB1E, 12 bytes

∞<*+ηPÅΔ₁Ö}>

Takes the inputs in reversed order, so step before start.

Try it online or verify all test cases.

Explanation:

∞             # Push an infinite positive list: [1,2,3,...]
 <            # Decrease each by 1 to let it start at 0: [0,1,2,...]
  *           # Multiply each by the first (implicit) input (step)
   +          # Add the second (implicit) input (start)
    η         # Get all prefixes of this infinite list
     P        # Take the product of each inner prefix-list
      ÅΔ      # Find the first (0-based) index which is truthy for:
        ₁Ö    #  Where the value is divisible by 256
          }>  # After we've found this index: increase it by 1 to make it 1-based
              # (after which the result is output implicitly)
\$\endgroup\$
0
\$\begingroup\$

Scala, 54 bytes

LazyList.from(_,_).scanLeft(1)(_*_)indexWhere(_%256<1)

Try it in Scastie!

Explanation:

LazyList.from(_,_) //Creates a LazyList starting at the first parameter with a step given by the second parameter.
  .scanLeft(1)(_*_) //scanLeft is like foldLeft, but keeps each result in a list
  indexWhere(_%256<1) //Find the index where it's divisible by 256
\$\endgroup\$
0
\$\begingroup\$

Haskell, 51 49 bytes

b#s=findIndex((<1).(`mod`256))$scanl(*)1[b,b+s..]

Try it online!

Port of my Scala answer

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

Rust, 58 bytes

|s,m|(|mut i,mut a|{while 0<a%256{a*=i;i+=m}(i-s)/m})(s,1)

Try it online!

A closure whose first argument is the first element of the sequence and whose second argument is the step.

Ungolfed with comments

//Initial element, step
|s,m|
  //i is initial value of s, a is accumulator
  (|mut i,mut a| {
    while 0 < a % 256 {   //while a is not divisible by 2^8
      a *= s;             //Multiply a by the current element of the sequence
      s += m              //Get the next element of the sequence by adding the step
    }
    //Subtract the initial value s to only keep increases of m, divide by m to get how many times it was increased
    (i - s) / m
  )
   (s, 1) //Call with i as s and initial value of accumulator as 1
\$\endgroup\$

Your Answer

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