This site is supported by donations to The OEIS Foundation.
User:M. F. Hasler/A307511
From OeisWiki
First values and Definition
The sequence A307511 starts 0, 1, 2, 222, 22, 2222, 3, 120, 10, 234, ...
Next term is the smallest a(n+1) not used before such that its concatenation with a(n) has the smallest possible number of distinct "sub-numbers" strictly larger than for the previous term. Here, a sub-number is a numeric substring: leading zeros are ignored, digits/characters must be taken consecutively from the full string.
Examples
- a(0) = 0 and a(1) = 1: "0"."1" = "01" has 2 sub-numbers: 0 and 1 (= 01).
- a(2) = 2: "1"."2" = "12" has 3 sub-numbers: 1, 2 and 12.
- "2"."222" = "2222" has 4 distinct sub-numbers: 2, 22, 222, and 2222. If we append any other single digit (or 22), it yields again 3 distinct substrings, not more than before. If we append another digit twice (e.g., 11 => 211), we get 5 distinct numeric substrings, which is not minimal.
- "222"."22" = "22222" has 5 distinct sub-numbers: 2, 22, 222, and 2222.
- "22"."2222" = "222222" has 6 distinct sub-numbers: 2, 22, 222, 2222, 22222 and 222222.
- Since "2" and "22" were already used, there is no possibility to produce a number with 7 or 8 sub-numbers.
- "0" and "1" also occurred earlier, so the smallest possible next terms is a(6) = 3:
- "2222"."3" = "22223" has 9 distinct sub-numbers: 2, 22, 222, 2222 and 3, 23, 223, 2223, 22223.
Programs
C++
#include <bits/stdc++.h> using namespace std; int debug=0; char buf[99]; typedef unsigned long long ull; // sufficiently large and sufficiently efficient for our purpose // This is an alternate variant, using strings, for double checking. int ns(char *s) { set<ull> S; //if(debug>2) cerr<<"entering n() with s="<<s<<endl; for(; *s; ++s){ ull n = *s - '0'; S.insert(n); if(n) for(char *e=s+1; *e; ++e) S.insert( n = n*10 + (*e - '0')); } return S.size(); } // We can assume that N has at least two nonzero digits. We'll never have N = 10^k. int n(ull N) { set<ull> S; //if(debug>2) cerr<<"entering n() with s="<<s<<endl; for(ull M=1; M<=N;){ ull O = M; M*=10; ull n = N % M; if( n < O ) // this n was already processed before, with smaller M S.insert(0); else do S.insert(n); while (n /= 10); } return S.size(); } main(int argc, char**argv){ int N=2; vector<ull>a = {1}; set<ull> U;/* "used" numbers */ vector<int>given_indices; vector<ull>given_values; ull STOP = 0; multiset<ull> jump={/*5,5,19,23,31,43*/};/* AFTER term with this index, increase N once more */ for(int i=0; ++i<argc;) switch( *argv[i]=='-' ? *++argv[i] : *argv[i] ){ case'a': given_indices.push_back( atoi( isdigit(argv[i][1]) ? argv[i]+1 : argv[++i] )); given_values.push_back( atoll( argv[++i] )); break; case'd': debug=(argv[i][1] ? atoi(argv[i]+1) : 1); break; case'n': char *s = (argv[i][1] ? argv[i]+1 : argv[++i]); cout << "n( "<< s <<" ) = "<< n(atoll(s)) << " (method 1: integer based)\n"; cout << " =?= "<< ns(s) << " (method 2: string based)\n"; break; case'h': printf("Usage: %s [OPTIONS] [JUMPS] where OPTIONS are among:\n" "\t[-]d<debug_level> | [-]{h[elp] | u[sage]} | [-]n<number>\n" "\t[-]a<index> <value> | [-]{x | q[uit]} | [-]s[top]<value>\n" "Dashes are optional. Args to options d, n, s can be preceded by a space.\n" "Option -nx prints n(x) (number of distinct substring-numbers) for given x, using two distinct methods.\n" "The -a option allows to specify the result for given indices (by-pass computation).\n" "The -s option allows to stop (end the computation and exit) when a given value is reached.\n" "Additional args [JUMPS] increase the lower search limit for n(x) at the given indices by +1.\n" ,argv[0]); // drop through and exit case'q': case'x': exit(0); case's': STOP = atoll( isdigit(argv[i][1]) ? argv[i]+1 : argv[++i]); break; case'j': if( isdigit(argv[i][1])) ++argv[i]; else ++i; default: jump.insert(atoll(argv[i]));// allow to add additional jumps as arguments } for(;;){ ull an=a.back(); U.insert(an); // add to "used numbers"; print it: //int L=sprintf(buf, "%llu", an); printf("/* %d (N=%d) */ %llu, ", a.size(), N, an); fflush(stdout); if(an==STOP) return 0; // for timing or so // require more substrings. N += 1+jump.count(a.size()); if(!given_indices.empty() && a.size()+1==given_indices[0]){ if(debug) cerr<<"/* Using given value: */ ", fflush(stderr); given_indices.erase(given_indices.begin()); a.push_back(given_values[0]); given_values.erase(given_values.begin()); // here we could check whether we need to increase N continue; // goto next index. } restart: auto next_Used = U.begin(); // next number to skip // If all numbers of given length lead to an n-value larger than N // then we're sure we can't find less when we increase the length of the number int n_min = INT_MAX; ull next_MAX = 10 // this is the next longer integer prefix = an*next_MAX; // avoiding this multiplication in the loop yields about 10% speed improvement for(ull k=1;; ++k) { if ( k == next_MAX ) { // doesn't happen often, no optimization needed below if( n_min > N && (!U.count(k/9*(an%10)) || n(an*next_MAX + k/9*(an%10))>N) ) { // do not increase if "n times the last digit" was in U ++N; cerr<<"/* increasing N to "<<N<<" */ ",fflush(stderr); goto restart; } next_MAX *= 10; n_min = INT_MAX; prefix *= 10; if(debug>1) cerr<<"/* next_max="<<next_MAX<<" */\n"; } if( k == *next_Used ) { // number already used if( ++next_Used == U.end()) next_Used = U.begin(); // and it will never be equal again } else { // sprintf(buf+L,"%llu",k); int n_buf = n(prefix + k); if( n_buf == N ) { a.push_back(k); break; /* FOUND ! */ } if(n_buf < n_min) { n_min = n_buf; /* k_min = k; */ } } } } }
PARI
Check out A307511 for the latest version.