Task — Binary prefix

You are given an array, @nums, where each element is either 0 or 1.

Define xi as the number formed by taking the first i+1 elements of @nums (from $nums[0] to $nums[i]) and interpreting them as a binary number, with $nums[0] being the most significant bit.

For example, if @nums is (1, 0, 1), then:

• x0 = 1 (binary 1)
• x1 = 2 (binary 10)
• x2 = 5 (binary 101)

Write a script to return an array @answer where $answer[$i] is true if xi is divisible by 5, otherwise false.

Examples

Example 1
Input: @nums = (0,1,1,0,0,1,0,1,1,1)
Output: (true, false, false, false, false, true, true,
   false, false, false)
Binary numbers formed (decimal values):
         0: 0
        01: 1
       011: 3
      0110: 6
     01100: 12
    011001: 25
   0110010: 50
  01100101: 101
 011001011: 203
0110010111: 407

Example 2
Input: @num = (1,0,1,0,1,0)
Output: (false, false, true, true, false, false)
     1: 1
    10: 2
   101: 5
  1010: 10
 10101: 21
101010: 42

Example 3
Input: @num = (0,0,1,0,1)
Output: (true, true, false, false, true)
    0: 0
   00: 0
  001: 1
 0010: 2
00101: 5

Example 4
Input: @num = (1,1,1,1,1)
Output: (false, false, false, true, false)
    1: 1
   11: 3
  111: 7
 1111: 15
11111: 31

Example 5
Input: @num = (1,0,1,1,0,1,0,0,1,1)
Output: (false, false, true, false, false, true, true,
   true, false, false)
         1: 1
        10: 2
       101: 5
      1011: 11
     10110: 22
    101101: 45
   1011010: 90
  10110100: 180
 101101001: 361
1011010011: 723

Analysis

For each element of @nums:

• I add it (0 or 1) to $sum.
• I add 'true' or 'false' to the output string according to whether $sum is a multiple of 5 or not.
• I multiply $sum by 2.

This will work provided $sum at the second step above does not exceed 2**63 - 1 = 9_223_372_036_854_775_807, which is - on my computer - the largest integer represented internally as its binary equivalent rather than as a floating point approximation.

Initially I determined whether a number was a multiple of 5 using $sum / 5 == int($sum / 5). However, after about 55 components of @nums this always returns true, which I think is due to exceeding the maximum number of bits allowed for the mantissa of a floating point number.

However my submitted solution uses $sum =~ m|[05]$| to check whether the last digit of $sum is 0 or 5, which works correctly up to 2**63 - 1, as evidenced by my last example.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2025-12-15
use utf8;     # Week 352 - task 2 - Binary prefix
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

binary_prefix(0, 1, 1, 0, 0, 1, 0, 1, 1, 1);
binary_prefix(1, 0, 1, 0, 1, 0);
binary_prefix(0, 0, 1, 0, 1);
binary_prefix(1, 1, 1, 1, 1);
binary_prefix(1, 0, 1, 1, 0, 1, 0, 0, 1, 1);
my @nums;
push @nums, 1 for 1 .. 63;
binary_prefix(@nums);

sub binary_prefix {
    
    my (@nums, $sum, $j, $output);
    
    # initialise
    @nums = @_;
    $sum = 0;
    
    # loop over @nums
    for $j (0 .. @nums - 1) {
        
        # add $nums[$j], ie 0 or 1
        $sum += $nums[$j];
        
        # true if $sum is a multiple of 5, else false
        $output .= ($sum =~ m|[05]$| ? 'true' : 'false') . qq[ ($sum), ];
        
        # shift $sum left
        $sum *= 2;
    }   
    
    say qq[\nInput:  (] . join(', ', @nums) . q[)];
    say qq[Output: ] . substr($output, 0, -2);
}

Output

Input:  (0, 1, 1, 0, 0, 1, 0, 1, 1, 1)
Output: true (0), false (1), false (3), false (6),
   false (12), true (25), true (50), false (101),
   false (203), false (407)

Input:  (1, 0, 1, 0, 1, 0)
Output: false (1), false (2), true (5), true (10),
   false (21), false (42)

Input:  (0, 0, 1, 0, 1)
Output: true (0), true (0), false (1), false (2), true (5)

Input:  (1, 1, 1, 1, 1)
Output: false (1), false (3), false (7), true (15),
   false (31)

Input:  (1, 0, 1, 1, 0, 1, 0, 0, 1, 1)
Output: false (1), false (2), true (5), false (11),
   false (22), true (45), true (90), true (180),
   false (361), false (723)

Input:  (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Output: false (1), false (3), false (7), true (15), 
   false (31), false (63), false (127), true (255), 
   false (511), false (1023), false (2047), true (4095), 
   false (8191), false (16383), false (32767), 
   true (65535), false (131071), false (262143), 
   false (524287), true (1048575), false (2097151), 
   false (4194303), false (8388607), true (16777215), 
   false (33554431), false (67108863), false (134217727), 
   true (268435455), false (536870911), 
   false (1073741823), false (2147483647), 
   true (4294967295), false (8589934591), 
   false (17179869183), false (34359738367), 
   true (68719476735), false (137438953471), 
   false (274877906943), false (549755813887), 
   true (1099511627775), false (2199023255551), 
   false (4398046511103), false (8796093022207), 
   true (17592186044415), false (35184372088831), 
   false (70368744177663), false (140737488355327), 
   true (281474976710655), false (562949953421311), 
   false (1125899906842623), false (2251799813685247), 
   true (4503599627370495), false (9007199254740991), 
   false (18014398509481983), false (36028797018963967), 
   true (72057594037927935), false (144115188075855871), 
   false (288230376151711743), false (576460752303423487), 
   true (1152921504606846975), 
   false (2305843009213693951), 
   false (4611686018427387903), 
   false (9223372036854775807)