🔢 mathematics

Cullen and Woodall numbers in Padovan and Perrin sequences

This paper identifies all intersections between Cullen and Woodall numbers and the Padovan and Perrin sequences, proving that 1 and 7 are the only Woodall numbers in the Padovan sequence while 3 is the sole Cullen number in the Perrin sequence.

Original authors: Herbert Batte, Eric F. Bravo, Florian Luca

Published 2026-05-25

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Herbert Batte, Eric F. Bravo, Florian Luca

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to find hidden treasures in two very long, mysterious number lines. These number lines are called the Padovan sequence and the Perrin sequence. They are generated by a simple rule: to get the next number, you add the number from two steps back to the number from three steps back. It's like a game of musical chairs where the numbers keep rearranging themselves according to a strict rhythm.

On the other side of the room, you have two special bags of "treasure coins."

Woodall coins are shaped like $m \cdot 2^m - 1$ .
Cullen coins are shaped like $m \cdot 2^m + 1$ .

These coins grow incredibly fast, doubling and doubling in size. The big question the authors of this paper asked was: "Do any of these special coins ever land exactly on a spot in the Padovan or Perrin number lines?"

The Mystery Solved

The authors, acting as mathematical detectives, went on a hunt to find every single match. Here is what they found:

In the Padovan Sequence (The Woodall Hunt):
They looked for Woodall coins ( $m \cdot 2^m - 1$ ) hiding in the Padovan line.
- The Result: They found only two matches. The number 1 (which is a Woodall number when $m=1$ ) and the number 7 (which is a Woodall number when $m=2$ ).
- The Conclusion: No other Woodall coins fit into the Padovan line. If you keep counting forever, you will never find another one.
In the Perrin Sequence (The Cullen Hunt):
They looked for Cullen coins ( $m \cdot 2^m + 1$ ) hiding in the Perrin line.
- The Result: They found only one match. The number 3 (which is a Cullen number when $m=1$ ).
- The Conclusion: No other Cullen coins fit into the Perrin line.

How Did They Solve It?

You might wonder, "How do you check an infinite number line?" You can't just count forever. The authors used a clever two-step strategy, like a detective narrowing down a suspect list.

Step 1: The "Magnifying Glass" (Linear Forms in Logarithms)
First, they used a powerful mathematical tool (Baker's theory) that acts like a super-magnifying glass. This tool allowed them to prove that if a match existed, it couldn't be too far out. It set a "ceiling" on how big the numbers could be.

Analogy: Imagine they proved that if a treasure exists, it must be buried somewhere within the first 500 million miles of the number line, rather than being lost in the infinite universe. This reduced the problem from "infinite" to "very large but finite."

Step 2: The "Fingerprint Scanner" (2-adic Valuation)
Even with the ceiling set, 500 million is still too many to check by hand. So, they used a second tool called 2-adic valuation. Think of this as a fingerprint scanner that looks at how many times a number can be divided by 2.

The Padovan and Perrin numbers have very specific, predictable "fingerprints" regarding how many times they can be divided by 2.
The Woodall and Cullen numbers have their own unique fingerprints.
The authors realized that for a match to happen, the fingerprints had to align perfectly. By analyzing these patterns, they realized that for most numbers, the fingerprints simply don't match.
Analogy: It's like trying to fit a square peg into a round hole. They proved that for almost all numbers, the "square peg" (the Woodall/Cullen number) is the wrong shape to fit into the "round hole" (the Padovan/Perrin number).

Step 3: The Final Sweep (Computer Check)
After using the math to shrink the search area down to a tiny, manageable size (checking numbers up to about 56 for Woodall and 51 for Cullen), they let a computer do the final work. The computer checked every single remaining possibility and confirmed: No other matches exist.

The Bottom Line

The paper is a definitive "closed case."

Woodall numbers in Padovan: Only 1 and 7.
Cullen numbers in Perrin: Only 3.

The authors didn't just guess; they used deep mathematical theory to rule out the infinite possibilities and then used a computer to verify the small leftovers. They proved that these sequences are like two different languages that rarely, if ever, speak the same word.

Technical Summary: Cullen and Woodall Numbers in Padovan and Perrin Sequences

Problem Statement
This paper addresses the intersection of two specific classes of exponential Diophantine numbers with linear recurrence sequences. Specifically, the authors investigate the presence of Woodall numbers (integers of the form $W_m = m \cdot 2^m - 1$ ) within the Padovan sequence $\{P_n\}$ , and Cullen numbers (integers of the form $C_m = m \cdot 2^m + 1$ ) within the Perrin sequence $\{R_n\}$ .

The Padovan and Perrin sequences are both defined by the recurrence relation $U_{n+3} = U_{n+1} + U_n$ , but with distinct initial conditions:

Padovan: $P_0 = P_1 = P_2 = 1$ .
Perrin: $R_0 = 3, R_1 = 0, R_2 = 2$ .

While previous work by Bravo and Irmak [4] had determined the Cullen numbers in the Padovan sequence and Woodall numbers in the Perrin sequence, the complementary cases (Woodall in Padovan, Cullen in Perrin) remained open. The authors aim to completely resolve these remaining cases.

Methodology
The proof strategy follows a standard framework for solving Diophantine equations in linear recurrence sequences, combining analytic number theory with computational verification:

Closed-Form Analysis: The authors utilize Binet-type formulas for both sequences, expressing terms as linear combinations of powers of the roots of the characteristic polynomial $\phi(X) = X^3 - X - 1$ . This allows for growth estimates and the derivation of inequalities bounding the indices $n$ and $m$ .
Linear Forms in Logarithms: To establish an absolute upper bound for the variable $m$ , the authors apply Matveev's theorem on linear forms in three logarithms of algebraic numbers. By constructing a linear form $\Lambda$ involving $\log 2$ , $\log \alpha$ (where $\alpha$ is the real root of $\phi(X)$ ), and $\log m$ , they derive a lower bound for $|\Lambda|$ . Comparing this with an upper bound derived from the recurrence growth leads to an initial, albeit large, upper bound for $m$ (approximately $5.6 \times 10^{14}$ for the Padovan case and $5.4 \times 10^{14}$ for the Perrin case).
2-adic Valuation Analysis: To reduce the massive bounds obtained from Matveev's theorem to a computationally feasible range, the authors perform a detailed analysis of the 2-adic valuation ( $\nu_2$ $ν_{2}$ ) of the shifted sequences $\{P_n + 1\}$ ${P_{n} + 1}$ and $\{R_n - 1\}$ ${R_{n} - 1}$ .
- They establish explicit formulas for $\nu_2(P_n + 1)$ and $\nu_2(R_n - 1)$ based on the residue of $n$ modulo specific integers (e.g., 112 for Padovan, 14 for Perrin).
- For "exceptional" residue classes where a uniform closed-form expression does not exist, they employ a greedy algorithm based on doubling recurrences (Lemmas 2.10 and 2.11) to compute the maximum possible valuation for $n$ within the previously established bounds.
- This analysis yields the inequality $m \leq \nu_2(\text{shifted term})$ , which drastically reduces the search space for $m$ .
Computational Verification: Once the bounds for $m$ are reduced to small constants (specifically $m \leq 56$ for Padovan and $m \leq 51$ for Perrin), the authors perform an exhaustive computational search using SageMath to check for solutions within the reduced ranges.

Key Contributions and Results
The paper provides complete solutions to the two open problems regarding Woodall and Cullen numbers in these specific sequences:

Theorem 1.1: The only Woodall numbers in the Padovan sequence are 1 and 7.
- Corollary 1.2: Consequently, the only Woodall prime in the Padovan sequence is 7.
Theorem 1.3: The only Cullen number in the Perrin sequence is 3.
- Corollary 1.4: Consequently, the only Cullen prime in the Perrin sequence is 3.

The proofs rely on the specific properties of the 2-adic valuations of $P_n + 1$ and $R_n - 1$ . Notably, the authors identify non-rational 2-adic zeros for these shifted sequences, which necessitated the algorithmic approach for the exceptional residue classes.

Significance and Claims
The authors position this work as the natural completion of the research initiated by Bravo and Irmak [4]. By determining the complementary sets of numbers, the paper fully characterizes the intersection of Woodall and Cullen numbers with the Padovan and Perrin sequences.

The significance lies in:

Completeness: It resolves the remaining open cases for these specific order-3 linear recurrence sequences.
Methodological Refinement: The paper demonstrates the necessity of analyzing the 2-adic valuations of shifted sequences ( $P_n+1$ and $R_n-1$ ) rather than the sequences themselves, highlighting the complexity introduced by the specific initial conditions and the form of the target numbers ( $m \cdot 2^m \pm 1$ ).
Algorithmic Application: The work utilizes and refines algorithms for computing 2-adic valuations in exceptional residue classes, providing explicit approximations of non-rational 2-adic zeros for these sequences.

The paper does not claim broader applications beyond the specific Diophantine problems addressed but contributes to the growing body of literature on the intersection of exponential Diophantine equations and linear recurrence sequences.

The Mystery Solved

How Did They Solve It?

The Bottom Line

More like this