24 October 2026

Challenge 016

Bitcoin Pie

• Task 1: Pythagoras Pie Puzzle
• Task 2: Validating Bitcoin addresses

Task 1: Pythagoras Pie Puzzle

Pythagoras Pie Puzzle, proposed by Jo Christian Oterhals.

At a party a pie is to be shared by 100 guest. The first guest gets 1% of the pie, the second guest gets 2% of the remaining pie, the third gets 3% of the remaining pie, the fourth gets 4% and so on.

Write a script that figures out which guest gets the largest piece of pie.

---

Solution

Here is my solution dated 15 Mar 2023:

use v5.16;
use warnings;
use List::Gen;
use List::UtilsBy 'max_by';

# Build a generator for 100 pie pieces.
my $parts = do {
    my $pie = 1;
    <1..100>->map(sub {
            my $part = $pie * $_ / 100;
            $pie -= $part;
            $part;
        }
    );
}->cache;

# Find the 1-based index of the maximum.
say scalar max_by {$parts->($_ - 1)} 1 .. 100;

Task 2: Validating Bitcoin addresses

Write a script to validate a given bitcoin address. Most Bitcoin addresses are 34 characters. They consist of random digits and uppercase and lowercase letters, with the exception that the uppercase letter “O”, uppercase letter “I”, lowercase letter “l”, and the number “0” are never used to prevent visual ambiguity. A bitcoin address encodes 25 bytes. The last four bytes are a checksum check. They are the first four bytes of a double SHA-256 digest of the previous 21 bytes. For more information, please refer wiki page. Here are some valid bitcoin addresses:

    1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2
    3J98t1WpEZ73CNmQviecrnyiWrnqRhWNLy

---

Solution

Following the Python validation provided at the Bitcoin Forum.

J

I wrote the J implementation as a prove of concept, just to have a valid checksum calculation in a language I am comfortable with. It does neither check the validity of of the input characters nor the input string’s length.

Created a tacit verb to perform the checksum verification.

validate_bitcoin_addr =: _(adverb define)
  NB. characters used to encode base-58
  B58Chars =. '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'

  NB. convert the string of base-58 characters in y to an extended integer
  B58toX =. (x: # B58Chars) #. B58Chars i. ]

  NB. convert an extended integer in y to a list of x base-256 digits
  XtoB256 =. ] #:~ 256 #~ [

  NB. convert a list of base-256 digits in y to a string of corresponding bytes
  B256toByte =. {.@(1&(3!:4))"0

  NB. drop the last four items from y (version and 160 bits)
  vh160 =. _4&}.

  NB. pick the last four items from y (checksum)
  chksum =. _4&{.

  NB. pick the first four items from y
  head =. 4&{.

  NB. calculate the twofold SHA256 digest for y
  DblSha256 =. _3&(128!:6)^:2

  NB. convert the base-58 string in y to 25 bytes,
  NB. calculate the twofold SHA256 digest over the first 21 bytes,
  NB. pick the first four bytes thereof and
  NB. compare these to the last four bytes from the converted string
  ((chksum -: head @ DblSha256 @ vh160) @: B256toByte @ (25&XtoB256) @ B58toX) f. : [:
)

See the full solution.

Perl

This is a straightforward port of the J solution to Perl with added checks for character set and string length.

use v5.26;
use strict;
use bigint;
use Math::Prime::Util qw(fromdigits todigits);
use Digest::SHA 'sha256';

sub validate_bitcoin_addr ($addr) {
    state $B58Chars = '123456789' .
        'ABCDEFGHJKLMNPQRSTUVWXYZ' .
        'abcdefghijkmnopqrstuvwxyz';
    $addr =~ /^[$B58Chars]{27,35}$/ or return 0;
    my @b58digits = map index($B58Chars, $_), split //, $addr;
    my $int = fromdigits \@b58digits, length $B58Chars;
    my @bytes = todigits $int, 256, 25;
    my $bytes = pack 'C*', @bytes;
    my $chk = substr sha256(sha256(substr $bytes, 0, 21)), 0, 4;
    $chk eq substr $bytes, -4 or 0;
}

See the full solution to task 2.