A019268 - OEIS

A019268

Let Dedekind's psi(m) = product of (p+1)p^(e-1) for primes p, where p^e is a factor of m. Iterating psi(m) eventually results in a number of form 2^x*3^y. a(n) is the smallest number that requires n steps to reach such a number.

1, 5, 13, 37, 73, 673, 1993, 15013, 49681, 239233, 1065601, 8524807, 68198461, 545587687, 1704961513, 7811750017, 97496942497, 244140624997, 488281249993, 19514376019981, 61033203124897

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

There is a remarkable and unexplained agreement: if 5 is dropped from the list, 2, 673, 1993 and 239233 are replaced by 1, 1021, 29173 and 532801, the result is sequence A005113 (least prime of class n+, according to the Erdős-Selfridge classification of primes).

A019269(a(n)) = n and A019269(m) != n for m < a(n). - Reinhard Zumkeller, Apr 12 2012

Erdos-Selfridge primes of class 1+ are primes p such that p+1 is of the form 2^x*3^y. Iterating the Dedekind psi function eventually produces a number of that form. Let p be a prime. Psi(p)=p+1, so except for psi(2)=3, the prime factors of psi(p) are < p. Psi is multiplicative, so consider psi(p^k), which is (p-1)*p^(k-1). Each iteration replaces a factor of p by primes that are < p. So, iterating psi reaches a number of the form 2^x*3^y. So some terms of this sequence are expected to match terms of A005113. - Jud McCranie, May 11 2026

REFERENCES

Peter Giblin, "Primes and Programming - an Introduction to Number Theory with Computing", page 118.

R. K. Guy, "Unsolved Problems in Number Theory", section B41.

LINKS

Table of n, a(n) for n=0..20.

MATHEMATICA

psi[m_] := ({pp, ee} = FactorInteger[m] // Transpose; If[Max[pp] == 3, m, Times @@ (pp+1)*Times @@ (pp^(ee-1))]); a[0] = 1; a[1] = 5; a[n_] := a[n] = For[k = a[n - 1] (* assuming monotony *), True, k++, If[Length @ FixedPointList[psi, k] == n+2, Return[k]]]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 10}] (* Jean-François Alcover, Feb 19 2018 *)

PROG

(Haskell)

import Data.List (elemIndex)

import Data.Maybe (fromJust)

a019268 = (+ 1) . fromJust . (`elemIndex` a019269_list)

-- Reinhard Zumkeller, Apr 12 2012

CROSSREFS

Cf. A005113, A082449.

Sequence in context: A375794 A058507 A111057 * A083413 A232879 A269803

Adjacent sequences: A019265 A019266 A019267 * A019269 A019270 A019271

KEYWORD

nonn,nice,more,changed