Zero the byte (eventually)

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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!

Answer 7

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)

Answer 8

J, ³⁰ 29 bytes

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

Try it online!

-1 byte thanks to Traws

Straightforward conversion of the algorithm into J.

Answer 9

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)

Answer 10

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!

Answer 11

Factor, 105 bytes

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

Try it online!

Answer 12

APL (Dyalog), 19 bytes

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

Try it online!

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

Answer 13

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.

Answer 14

Charcoal, 24 bytes

⊞υＮＮηＷ﹪ΠＥυΣ…υ⊕λ²⁵⁶⊞υηＩＬυ

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

⊞υＮ

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

Ｎη

Input the step.

Ｗ﹪ΠＥυΣ…υ⊕λ²⁵⁶

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.

ＩＬυ

Output the length of the list.

Answer 15

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.

Answer 16

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)

Answer 17

C (gcc), ⁴⁶ 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 */
}

Answer 18

Wolfram Language (Mathematica), 59 bytes

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

Try it online!

Answer 19

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.

Answer 20

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)

Answer 21

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

Answer 22

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

Answer 23

Haskell, 51 49 bytes

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

Try it online!

Port of my Scala answer