Arithmetic properties of sequences

Dold, Newton and realizable sequences, Sylvester, Euclid and Göbel sequences, gcd and divisibility sequences, OEIS-specific sequences.

• Arithmetic terms for the greatest common divisor
• Binomial sum parities and cotangent floor sequences
• Complementary sequences
• Dold and realizable sequences
• Göbel sequences
• Integer complexity
• Arithmetical self-similar compact sets
• Newton sequences
• Sets of remainders
• Sylvester's sequence

DefinitionMultiple-counting Jacobsthal sequence#✓fully proved

For natural numbers \(x\), \(\rho\) and \(n\), the multiple-counting Jacobsthal sequence \(J_{x,\rho}(n)\) is the number of multiples of \(\rho\) strictly between \(x^n\) and \(x^{n+1}\), that is, the number of natural numbers \(k\) with \(x^n < k < x^{n+1}\) and \(\rho \mid k\).

The source studies \(2 \le x\) and \(2 \le \rho\); the count itself is useful without those restrictions.

def multipleCountingJacobsthalSequence (x rho n : ℕ) : ℕ :=
  ((Finset.Ioo (x ^ n) (x ^ (n + 1))).filter (fun k => rho ∣ k)).card

Sources

• https://cs.uwaterloo.ca/journals/JIS/VOL19/Cilasun/cila5.tex.

DefinitionOdd Lichtenberg numbers#✓fully proved

The odd Lichtenberg numbers form the sequence \((a_n)_{n \ge 0}\) of natural numbers defined by \(a_0 = 1\) and \(a_{n+1} = 4 a_n + 1\), so the sequence begins \(1, 5, 21, 85, \dots\); these are the positive terms of OEIS A002450.

Equivalently, it is the self-generating sequence with seed \(1\) and generating function \(k \mapsto 4k + 1\).

def oddLichtenberg : ℕ → ℕ
  | 0 => 1
  | n + 1 => 4 * oddLichtenberg n + 1

Sources

• https://cs.uwaterloo.ca/journals/JIS/VOL25/Hinz/hinz5.tex.

TheoremSome generalized Euclid sequence contains every prime#✓fully proved

Let \(P\) be a finite set of primes and let \(k\) be the number of elements of \(P\). Then there is an injective sequence \(a_0, a_1, a_2, \dots\) of primes such that \(a_0, \dots, a_{k-1}\) are exactly the elements of \(P\), every prime occurs in the sequence, and for every \(n \ge k\) there is a set \(I \subseteq \{0, \dots, n-1\}\) such that \(a_n\) divides

\[\prod_{i \in I} a_i + \prod_{i \in \{0, \dots, n-1\} \setminus I} a_i.\]

This is an existence claim over all choices of \(I\) and of the prime divisor, unlike the open Euclid–Mullin conjecture about one specific sequence. For distinct primes \(p_1, \dots, p_r\) and any \(J \subseteq \{1, \dots, r\}\), the number \(\prod_{i \in J} p_i + \prod_{i \in \{1, \dots, r\} \setminus J} p_i\) is coprime to \(p_1 \cdots p_r\), so a prime divisor of it is always new.

Proof: Booker's residue-set route, with an elementary squarefree count in place of Rogers' density bound and Jacobi-sum character-sum bounds in place of the Hasse and Weil bounds.

public theorem generalized_euclid_sequence_contains_every_prime
    (P : Finset ℕ) (hP : ∀ p ∈ P, Nat.Prime p) :
    ∃ a : ℕ → ℕ, (∀ i, Nat.Prime (a i)) ∧ Function.Injective a ∧
      (∀ i < P.card, a i ∈ P) ∧ (∀ p ∈ P, ∃ i < P.card, a i = p) ∧
      (∀ n, P.card ≤ n → ∃ I : Finset ℕ, I ⊆ Finset.range n ∧
        a n ∣ (∏ i ∈ I, a i) + ∏ i ∈ (Finset.range n \ I), a i) ∧
      (∀ p, Nat.Prime p → ∃ i, a i = p)

Sources

• Andrew R. Booker, "A Variant of the Euclid-Mullin Sequence Containing Every Prime," Journal of Integer Sequences 19 (2016), Article 16.6.4, Theorem, lines 132–136, https://cs.uwaterloo.ca/journals/JIS/VOL19/Booker/book3.tex

3 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.