Vtyjkyuk

I've just finished the recent Numberphile video on Pascal's Triangle and learned about a new-to-me property of the triangle; the Fermat primes $F_0 = 3, F_1 = 5, F_2 = 17, dots$ are encoded in it somehow!

Take the standard Pascal's Triangle $(mod 2)$ and read out each row $r_n$ as binary, $x_n = sum_i=0^n 2^ir_n,i$ then the first few rows read as 1, 3, 5, 15, 17, 51, 85, 255, 257, … These are either Fermat primes or products of Fermat primes!

I wrote a short Python Script to explore a bit. The first few rows present an elegant binary pattern, $x_n = prod_i=0^n F_i^r_n,i$ selecting $3, 5, 3 times 5, 17, 3 times 17$, etc. This pattern is striking in its precision.

I wanted to know what happens around row 32/33, when we reach the Fermat non-prime $F_5 = 2^2^5+1 = 4294967297 = 641 times 6700417$. The pattern breaks, and $F_5$ shows up. However, on the next few rows, we have $12884901891 = 3 times 641 times 6700417, 21474836485 = 5 times 641 times 6700417, dots$ So this means that Fermat numbers specifically, rather than just some certain primes, are part of this overall correspondence. Additionally, we can see that the binary pattern repeats here, and it goes through all of the same permutations as earlier, but with the two new factors from $F_5$. $F_6$ also adds two more factors and repeats the pattern. I haven't yet explored higher.

I would like to know why this correspondence exists and what it might tell us about Fermat numbers. Personally, I found this jaw-dropping.

It is indeed true that each $x_n$ is a product of integers of the form
$2^2^m+1$ (although not of the ones you have stated).

To prove this, we fix an $ninmathbbN$. Your definition of $x_n$ rewrites
as $x_n=sumlimitslimits_substackiinleft 0,1,ldots,nright
;\dbinomnitext is odd2^i$.

Write $n$ in the form $n=a_k2^k+a_k-12^k-1+cdots+a_02^0$ for some
$kinmathbbN$ and $a_0,a_1,ldots,a_kinleft 0,1right $.
(This is just the base-$2$ representation of $n$, possibly with leading zeroes.)

Lucas's theorem tells you
that if $i=b_k2^k+b_k-12^k-1+cdots+b_02^0$ for some $b_0
,b_1,ldots,b_kinleft 0,1right $, then

$dbinomniequivdbinoma_kb_kdbinoma_k-1b_k-1
cdotsdbinoma_0b_0=prodlimits_j=0^kunderbracedbinoma_jb_j
_substack=
begincases
1, & textif b_jleq a_j\
0, & textif b_j>a_j
endcases
\text(since a_jtext and b_jtext lie in left 0,1right
text)$

$=prodlimits_j=0^k
begincases
1, & textif b_jleq a_j\
0, & textif b_j>a_j
endcases
=
begincases
1, & textif b_jleq a_jtext for all jtext;\
0, & textotherwise
endcases
mod 2$.

Hence, the $iinmathbbN$ for which $dbinomni$ is
odd are precisely the numbers of the form $b_k2^k+b_k-12^k-1
+cdots+b_02^0$ for $b_0,b_1,ldots,b_kinleft 0,1right $
satisfying $left( b_jleq a_jtext for all jright) $.
Since all these $i$ satisfy $i in left 0,1,ldots,nright$
(because otherwise, $dbinomni$ would be $0$ and therefore could not
be odd), we can rewrite this as follows: The
$i in left 0,1,ldots,nright$ for which $dbinomni$ is
odd are precisely the numbers of the form $b_k2^k+b_k-12^k-1
+cdots+b_02^0$ for $b_0,b_1,ldots,b_kinleft 0,1right $
satisfying $left( b_jleq a_jtext for all jright) $.
Since these
numbers are distinct (because the base-$2$ representation of any
$iinmathbbN$ is unique, as long as we fix the number of digits), we thus
can substitute $b_k2^k+b_k-12^k-1+cdots+b_02^0$ for $i$ in the
sum $sumlimitslimits_substackiinleft 0,1,ldots,nright ;\
dbinomnitext is odd2^i$. Thus, this sum rewrites as follows:

$sumlimits_substackiinleft 0,1,ldots,nright ;\
dbinomnitext is odd2^i
=underbracesumlimits_substackb_0,b_1
,ldots,b_kinleft 0,1right ;\b_jleq a_jtext for all j
_=sumlimits_b_0=0^a_0sumlimits_b_1=0^a_1cdotssumlimits_b_k=0^a_k
underbrace2^b_k2^k+b_k-12^k-1+cdots+b_02^0_=left(
2^2^kright) ^b_kleft( 2^2^k-1right) ^b_k-1cdotsleft(
2^2^0right) ^b_0$

$=sumlimits_b_0=0^a_0sumlimits_b_1=0^a_1cdotssumlimits_b_k=0^a_k
left( 2^2^kright) ^b_kleft( 2^2^k-1right) ^b_k-1
cdotsleft( 2^2^0right) ^b_0$

$=left( sumlimits_b_k=0^a_kleft( 2^2^kright) ^b_kright)
left( sumlimits_b_k-1=0^a_k-1left( 2^2^k-1right) ^b_k-1
right) cdotsleft( sumlimits_b_0=0^a_0left( 2^2^0right)
^b_0right) $

$=left( sumlimits_b=0^a_kleft( 2^2^kright) ^bright) left(
sumlimits_b=0^a_k-1left( 2^2^k-1right) ^bright) cdotsleft(
sumlimits_b=0^a_0left( 2^2^0right) ^bright) $

$=prodlimits_g=0^kunderbraceleft( sumlimits_b=0^a_gleft( 2^2^g
right) ^bright) _substack=
begincases
2^2^g+1, & textif a_g=1;\
1 & textif a_g=0
endcases
\text(since a_ginleft 0,1right text)$

$=prodlimits_g=0^k
begincases
2^2^g+1, & textif a_g=1;\
1 & textif a_g=0
endcases
$

$=left( prodlimits_substackginleft 0,1,ldots,kright ;\a_g
=1left( 2^2^g+1right) right) underbraceleft( prodlimits
_substackginleft 0,1,ldots,kright ;\a_g=01right) _=1$

$=prodlimits_substackginleft 0,1,ldots,kright ;\a_g=1left(
2^2^g+1right) $.

Thus, $x_n=sumlimits_substackiinleft 0,1,ldots,nright
;\dbinomnitext is odd2^i=prodlimits_substackginleft
0,1,ldots,kright ;\a_g=1left( 2^2^g+1right) $. This is clearly a product of Fermat numbers.

EDIT: This result also appears as equation (10) in Andrew Granville, Binomial coefficients modulo prime powers, 1997, where it is ascribed to Larry Roberts.

The claim is an example of the "law of small numbers".

The numbers you are looking at are products of the Fermat numbers $2^2^n + 1$, and not the Fermat primes. Since the first few such numbers are Fermat primes, but no larger Fermat primes are known, it is not surprising at all that the pattern holds for the first few $n$ and then fails at 32. It will continue to fail over and over again at larger row numbers.

More specifically, if $n = sum_0 leq i leq t a_i 2^i$, the identity is $sum_0 leq i leq n (n choose i bmod 2) 2^i = prod_0 leq j leq t (2^2^j+1)^a_j$. This is indeed a nice identity, but it has virtually nothing to do with primes or Fermat primes.

There is a 1977 article, "A Relationship Between Pascal's Triangle And Fermat's Numbers" (link to PDF), which provides a proof by induction that the number you call $x_n$ is equal to
$$F_k^d_kcdots F_0^d_0$$
where $n=(d_kldots d_0)_2$ is the binary expansion of $n$.