-1
$\begingroup$

Given a set of decimal digits. And given a set of primes $\mathbb{P}$, find some $p \in \mathbb{P}$ such that $p^n, n \in \mathbb{N} $ contained in itself all the digites from a given set, and it does not matter in what order.

$\endgroup$

closed as unclear what you're asking by B. Mehta, Hagen von Eitzen, Delta-u, J.R., jvdhooft May 25 '18 at 23:51

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ You mean, you are given something like 0,1,4,5,6,7,8 and a possible answer the algotithm should find might be $7^8 = 5764801$? $\endgroup$ – Hagen von Eitzen May 25 '18 at 13:22
  • $\begingroup$ Yep.............. $\endgroup$ – Vladislav Kharlamov May 25 '18 at 13:23
  • $\begingroup$ Moreover, an algorithm is desirable that constructs at least a finite set of such examples, not the cardinality of the set 1 $\endgroup$ – Vladislav Kharlamov May 25 '18 at 13:24
  • 1
    $\begingroup$ The longer you explain in reply to comments, the less clear the problem statement gets $\endgroup$ – Hagen von Eitzen May 25 '18 at 14:36
  • 1
    $\begingroup$ The lesson is to think clearly about what you are asking. In the spirit of my answer, any large power of a prime will have lots of digits so will almost certainly include at least one of each (but $2^{99}$ is missing $9$). For any $p$ you have very good odds that $p^{10000}$ will satisfy your need. $\endgroup$ – Ross Millikan May 25 '18 at 15:04
3
$\begingroup$

$2^{100}=1267650600228229401496703205376$ includes all the digits so it will answer your request for any set.

For any given prime it is believed that there is a highest power that does not contain all the digits, so if your list of primes doesn't include $2$ I would just raise one of them to the $1000$ power and expect it to be good. Proving that there is a highest power seems to be hard.

$\endgroup$
  • $\begingroup$ Is this the first power of $2$ that has all ten digits? $\endgroup$ – Barry Cipra May 25 '18 at 14:59
  • $\begingroup$ @BarryCipra: I doubt it. I started with powers around $50$ and found at least one digit missing, then jumped to $2^{99}$ which is missing $9$. I was just computing in Alpha and looking. Next I tried $100$ and found them all. $\endgroup$ – Ross Millikan May 25 '18 at 15:01
  • $\begingroup$ I wonder if there is a largest power of $2$ that doesn't contain each digit at least once.... $\endgroup$ – Barry Cipra May 25 '18 at 15:11
  • 1
    $\begingroup$ @BarryCipra $2^{68}$ is the first power of $2$ that contains all digits, followed by $70,79,82,84,87,88,89,94$ $\endgroup$ – B. Mehta May 25 '18 at 15:31
  • $\begingroup$ @BarryCipra: I believe that has been asked here. I am sure there is-once you have enough digits you are almost sure to get them all, but I suspect it is very hard to prove. This and this ask it. No solutions are given. $\endgroup$ – Ross Millikan May 25 '18 at 15:35
2
$\begingroup$

Remark: this answer pertains to the initial version of the question. The current edit restricts the search to powers within a given set of primes.

Another theoretically "cheap" way to look for prime powers that contain a given set of digits is to concatenate the $n$ digits, append a $1$ to get an $(n+1)$-digit number $d$ and then apply Dirichlet's theorem on primes in arithmetic progressions to the progression $10^{n+2}m+d$ for $m=1,2,3,\ldots$. (Appending the $1$ is necessary when, for example, the given digits are all even, in order to get a number $d$ that is relatively prime to $10$.) Dirichlet's theorem guarantees you'll find a prime, which can be checked for successive values of $m$ using, say, the AKS primality test if $n$ is large. If $n$ is small, say $n\approx10$, just about any primality test will do. Furthermore, the Prime Number Theorem (for primes in arithmetic progression) suggests you should find a prime relatively quickly.

$\endgroup$
1
$\begingroup$

More is true:

For any finite sequence of decimal digits, there is a power of $2$ whose decimal expansion begins with these sequence.

See here for a proof. For algorithms, see this question.

On the other hand, I've just run a computer search and every allowed subset of digits are the digits of a prime less than 304456880. Not all subsets of digits are allowed, of course: those whose sum is a multiple of $3$ are not. Nor are those solely composed of even digits. I've found $78$ forbidden subsets.

$\endgroup$
  • $\begingroup$ I know, but here we need an algorithm $\endgroup$ – Vladislav Kharlamov May 25 '18 at 13:53
  • $\begingroup$ There's an obvious algorithm: start at $1$ and keep multiplying by $2$ until you get a number that contains the digits you're looking for. The theorem guarantees the process will produce an answer. (It doesn't say how quickly, but that's a different question.) $\endgroup$ – Barry Cipra May 25 '18 at 13:57
  • $\begingroup$ Well, it would be nice to somehow improve, but so well. $\endgroup$ – Vladislav Kharlamov May 25 '18 at 14:00
  • $\begingroup$ How have you concluded that multiples of $3$ and even digits are disallowed? Recall that OP asks for prime powers, not just primes. In addition, primes like $277$ give the set $\{2,7\}$, which has a sum a multiple of 3. $\endgroup$ – B. Mehta May 25 '18 at 14:23
  • $\begingroup$ Fair, but this still leaves numbers such as $243 = 3^5$ missing. $\endgroup$ – B. Mehta May 25 '18 at 14:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.