Smallest Number with Given Multiplicative Persistence
Autumn Tournament (2018)
Submission name: persistence.cpp
Problem summary
Repeatedly replace a nonnegative integer by the product of its decimal digits, stopping at one digit. Find the smallest starting number needing exactly P replacements.
Input
P.
Output
The smallest nonnegative integer with persistence P.
Constraints
0 ≤ P ≤ 11; the answer is guaranteed to be less than 10^18.
Worked example
Original statement sample.
Input
7
Output
68889
Solution analysis
- Handle P=0 with answer 0 and P=1 with answer 10. For larger persistence, a minimum answer contains neither 0 nor 1: a zero immediately gives a one-digit product, while deleting a 1 leaves the product unchanged and makes the starting number smaller.
- Permuting the digits does not change their first product. Therefore a smallest answer must have digits in nondecreasing order. Enumerate such digit strings using only 2 through 9, first by increasing length and then lexicographically. Keep the accumulated number and digit product during a short recursive search; at a completed candidate, its persistence is 1 plus the directly computed persistence of that product.
- For P=3, the first successful candidate is 39: 39→27→14→4. For P=7, enumeration reaches 68889, whose successive products are 27648,2688,768,336,54,20,0. This has exactly seven replacements. No huge table of all integers below the answer is needed.
Why it works
For P≥2 the digit exclusions preserve the first product and strictly improve any candidate containing 1; zero is impossible. Sorting the remaining digits preserves persistence and minimizes their arrangement. The search visits every possible sorted multiset of at most eighteen digits in increasing numerical order, so the first successful candidate is globally minimal.
Watch out. Do not brute-force consecutive integers up to the answer. Persistence counts transformations, not intermediate values. The special answer 10 for P=1 uses a zero and must be handled before excluding digits 0 and 1.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
int persistence(long long value){
int steps=0;
while(value>=10){
long long product=1;
while(value>0){
product*=value%10;
value/=10;
}
value=product;
steps++;
}
return steps;
}
bool search(
int remaining,int smallestDigit,long long number,long long product,int wanted,long long&answer){
if(remaining==0){
if(1+persistence(product)==wanted){
answer=number;
return true;
}
return false;
}
for(int digit=smallestDigit;digit<=9;digit++){
// Nondecreasing digits enumerate each multiset exactly once.
if(search(remaining-1,digit,number*10+digit,product*digit,wanted,answer)){
return true;
}
}
return false;
}
int main(){
int wanted;
cin>>wanted;
if(wanted==0){
cout<<0<<'\n';
return 0;
}
if(wanted==1){
cout<<10<<'\n';
return 0;
}
long long answer=0;
for(int length=2;length<=18;length++){
if(search(length,2,0,1,wanted,answer)){
cout<<answer<<'\n';
break;
}
}
}