This site is supported by donations to The OEIS Foundation.

User:M. F. Hasler/A307511

From OeisWiki
Jump to: navigation, search

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.