2

This is an interesting question because for very small $p$, we already know the answer: for $p = 2, 3, 5, 7$, the answers are $1$ and $2$, $8$ and $9$, $80$ and $81$, and $4374$ and $4375$, respectively. Is there a formula for these kind of numbers for higher $p$, an algorithm with bounded time/space, or, failing that, at least an entry for this on OEIS?

Juniven Acapulco
  • 9,654
bootmii
  • 21
  • 1
    Yes, there is a constructive algorithm with bounded time (and therefore bounded space). This was first proved by Størmer: https://en.wikipedia.org/wiki/Størmer%27s_theorem – Erick Wong Dec 26 '16 at 03:44
  • Some details for a more general version of this problem are worked out in Eric Towers's answer here: http://math.stackexchange.com/a/724208/30402. It is still exponential-time in the number of factors. – Erick Wong Dec 26 '16 at 03:49

1 Answers1

1

Yes, you can derive it from A145606. I found it by searching on $80,4374$ from your post. The OEIS entry observes that the list is not monotonic, so you would replace $5142500$ with $11859210$ as both $11859210,11859211$ are $19$ smooth and $5142500$ is the entry for $23$ smooth

Ross Millikan
  • 374,822