Lesson progress0 / 10 missions
Chapter 26 · Decimal and Binary Numeration

Use Bit Patterns for Powers, Divisibility, and Subsets

A binary pattern can be more than a numeral. It can expose a factor, record a take-or-leave choice, or index one subset without listing every case.

Grade 510 missionsDivisibilityBit masksWorks offline
Your progress is saved in this browser.
The big idea

Read a bit pattern as an instruction

In this lesson, the same 0–1 language does three jobs:

Power pattern (positive integer n): 2n−1 is written as n consecutive 1-bits.
Factor pattern: grouping those bits into equal blocks can reveal divisibility.
Choice pattern: 1 means “take this item,” while 0 means “leave it.”

Three reusable translations

2n−1=(11…1)2, with n consecutive 1-bits
1 = take,    0 = leave
2n masks = 2n subsets

The empty mask 000…0 is one subset. Excluding it leaves 2^n-1 nonempty subsets.

1
Power-pattern foundation

Turn 2ⁿ − 1 into a ribbon of 1-bits

Not complete
n8
2ⁿ256
2ⁿ − 1255
1-bits8
Why? In binary, 1000…0₂ is a power of two. Subtracting 1 turns the leading 1 into a full row of lower-place 1s.
Pattern checkpoint.
Need a hint?

Subtracting 1 from a power of two fills all lower places with 1s.

2
Exercise 8

Group eighteen 1-bits to prove divisibility by 7

Not complete
original target: prove that 218−1 is divisible by 7.
1. 218−1 is eighteen 1-bits in binary.
2. Divide the ribbon into six blocks of 111₂.
3. Every 111₂ block has value 4+2+1=7; shifting it three places multiplies it by 23, but keeps the factor 7.
218−1=7(1+23+26+29+212+215)
decimal value262,143
block count6
block value7
quotient37,449
original-proof checkpoint.
Need a hint?

One block 111₂ is worth 7; count the three-bit blocks.

3
General block laboratory

Use equal blocks to prove repunit divisibility

Not complete
blocks3
block value 2ᵏ−115
long value 2ⁿ−14095
quotient273
Reusable result: A binary repunit is a numeral made entirely of 1s. For positive integers n and k, when k divides n, the block 2^k-1 divides 2^n-1.
Generalization checkpoint.
Need a hint?

Divide the ribbon length by the block length.

4
Exercise 10

Use paired bits to prove divisibility by 3

Not complete

Optional remainder notation: “a ≡ b (mod 3)” means a and b leave the same remainder when divided by 3. Since 2 is one less than 3, multiplying two such factors leaves remainder 1. The paired-bit proof below does not require this notation.

original target: prove that 222−1 is divisible by 3.

Binary-block proof

Twenty-two 1-bits make eleven copies of 11₂. Each block has decimal value 3.

222−1=3(1+22+24+⋯+220)

Remainder-cycle check

2≡−1 (mod 3)→2²≡1→2²²≡1→2²²−1≡0

This is an added second language for the same result. The worked example chapter’s binary pattern remains the main route.

1-bits22
2-bit blocks11
block value3
quotient1,398,101
Pair-block checkpoint.
Need a hint?

Pair the 22 one-bits into blocks of 11₂.

5
Exercise 11

Pair an alternating power sum to expose factors of 5

Not complete
S=215−214+213−212+⋯+2−1

Reduced binary pattern

101010101010101₂ uses the even powers from 214 down to 20.

Exact values

S21,845
S ÷ 54,369
S=5(212+28+24+1)
Alternating-sum checkpoint.
Need a hint?

Pair neighboring terms twice to expose a factor of 5.

6
Exercise 9

Use five bits to choose sugar bags

Not complete
original setup: five whole bags contain 1,2,4,8,16 kilograms. Each bag is either taken or left.
mask00000
selected total0 kg
all subsets32
positive totals31
0 through 31 kg are represented exactly once
Whole-bag checkpoint.
Need a hint?

Include the all-zero mask only when counting all subsets.

7
General subset-mask laboratory

Separate number of subsets from number of distinct totals

Not complete

Treat every listed item as separately selectable, even when two weights are equal. Each item can be taken at most once; item order in the list fixes mask positions from left to right. Totals include the empty choice, 0. A collision example: with boxes 1, 2, and 3, taking the 3-box and taking the 1- and 2-boxes are different subsets with the same total. There are eight masks, but only seven different totals: 0 through 6.

items5
subsets32
distinct totals32
first missing total from 0 through the sum of all weightsnone

Total-frequency bars

Mask ledger

Important: 2^n always counts the masks. It counts distinct totals only when different masks never collide.
Collision-and-gap checkpoint.
Need a hint?

Different subsets can have the same total; list totals from zero upward.

8
Test 26, Question 12

Use a binary mask to index powers-of-three subset sums

Not complete
Assessment transfer: choose any nonempty subset of 1,3,9,27,81,243, using each number at most once. Sort the 63 resulting sums from smallest to largest, numbering them from 1. Find the 39th.
39
binary mask100111
selected powers4
subset sum256
nonempty sums63
Why rank equals mask number: each power of 3 is greater than the sum of all smaller powers. Compare two masks at their first differing bit from the left; their higher bits are identical. The mask with 1 there has a greater sum, whatever its lower bits are. Thus binary mask order and increasing sum order agree.
Assessment checkpoint.
Need a hint?

Write the rank in binary and match its bits to the displayed powers of three.

9
Independent practice

Bit-pattern workshop

Not complete

Correct all eight answers to complete the workshop. Write counts and totals in decimal; only Question 7 asks for a bit mask.

Need a hint?

Answers: 10; 3; 15; 11; 21,845; 31; 10011; 256. Each mask bit makes one take/leave choice. For 19, take 16+2+1. For rank 39, mask 100111 selects 243+9+3+1.

10
Mastery check

Exit ticket and certificate

Not complete
Need a hint?

Answers: 111111111₂; 1057; 4369; 63; 30. Three five-bit blocks give quotient 1+2⁵+2¹⁰=1057. Six bags give 64 masks, of which 63 are nonempty. Rank 10 has mask 001010, selecting 27+3=30.