<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"><HTML DIR=ltr><HEAD><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"></HEAD><BODY><DIV><FONT face='Arial' color=#000000 size=2>
<DIV class=qt id=qhide_984584 style="DISPLAY: block">Hello SeqFan,</DIV>
<DIV class=qt style="DISPLAY: block">This came to me via rec.puzzles -- any
comment?</DIV>
<DIV class=qt style="DISPLAY: block">Best,</DIV>
<DIV class=qt style="DISPLAY: block">E.</DIV>
<DIV class=qt style="DISPLAY: block"> </DIV>
<DIV class=qt
style="DISPLAY: block">-------------------------------------------------------------------</DIV>
<DIV class=qt style="DISPLAY: block"> </DIV>
<DIV class=qt style="DISPLAY: block">Eric A. wrote: <BR>> Hello, <BR>>
isn't A096779 a finite sequence? <BR>> <A
href="http://www.research.att.com/~njas/sequences/A096779" target=_blank><FONT
color=#0000cc>http://www.research.att.com/~njas/sequences/A096779</FONT></A>
<BR>> If I'm not wrong, for n=1023456789 there is no <BR>> possible
a(n)... <BR>
<P>> A096779 says: <BR>> Smallest number not occurring earlier having in
its <BR>> decimal representation no common digit with n. <BR>
<P>> 2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 20, 30, 22, 23, 24,... <BR>
<P>> What could be this last term? <BR></P>
<P>[Sasha Semenov]:</P>
<P><BR>It looks like there is no elegant solution of this problem, <BR>that's
where the brute force approach should be applied. <BR></P>
<P>Lets scatter the entire set of positive integers into 2^10=1024 <BR>subsets,
<BR>depending on what decimal digits its deciaml representation contains.
<BR></P></DIV>
<P>Say the number 1121122909090 contains digits {0129}, and therefore
<BR>belongs to a subset indexed by binary number 1000000111. <BR>The most
significant bit set to 1 because 9 is here, and the least <BR>signifint
<BR>digits are set to 111 too because digits 2,1,0 are also in this number. <BR>
<P>Each number belongs to exactly one subset, they do not intyersect. <BR>
<P>If n belongs to subset indexed by index1, then A(n) belongs to <BR>one of
complementary subsets index2, which can "mate" with <BR>original subset. Two
subsets can mate if their indexi have no common <BR>ones, that is <BR>
<P>index1 (bit_wise_AND) index2 = 0 <BR>
<P>Note that if n1 and n2 belong to the same subset and
<BR>n1<n2,. then A(n1) < A(n2). As a consequence, taking <BR>into account
that A(A(n)) = n, one can conclude that <BR>the inverse statement is
also always true: <BR>
<P>if A(n1) and A(n2) both belong to the same subset, <BR>then
A(n1)<A(n2) => n1<n2.
<BR>
<P>Therefore the members of each subset enter into A(n) <BR>consequentially, and
without gaps. This is unlike the entire set <BR>positive integers, which
contains pockets of unused numbers <BR>between those already used in the
sequence A(n). <BR>
<P>Which means that instead of remembering which numbers <BR>are already in the
sequence, we can fully describe <BR>the state of sequence construction by only
1024 numbers - <BR>one "next available" member from each of 1024 subsets. <BR>
<P>A simple C++ program posted below produces the following <BR>result in about
5 minutes @ 1GHz CPU. <BR>
<P>Sequence member A(123456788): <BR>Length: 16, number: 9099900999090090 <BR>
<P>Sequence member A(123456780): <BR>Length: 5929, number:
99999999999999999999999999999999... <BR>
<P>#include <stdlib.h> <BR>#include <stdio.h> <BR>#include
<string.h> <BR>
<P>struct StrNumber <BR>{ <BR> char *repr_str; <BR>
long repr_len, buff_len; <BR>
<P>
<DIV class=qt id=qhide_984585 style="DISPLAY: block">}; <BR><BR></DIV>void
initSubSets(); <BR>void increment(StrNumber* n); <BR>void findNextInSubset(short
index); <BR>void addMSDigit(StrNumber* n); <BR>void printStrNumber(StrNumber*
n); <BR>void makeZeroStrNumber(StrNumber* n); <BR>short
getSubsetIndex(StrNumber* n); <BR>bool firstGreaterThanSecond(StrNumber* n1,
StrNumber* n2); <BR>
<P>StrNumber subset_top[0x400]; // tops of each subset <BR>short
*trellis[0x400]; // liast of indexes of subsets that mate <BR>short
trellis_len[0x400]; // list length <BR>
<P>int main(int narg, char **argv) <BR>{ <BR>
<P> StrNumber N, Target; <BR> short i; <BR>
<P> // set Tareget to specified aregument <BR> if
(narg != 2) <BR> { <BR>
printf("Useage:\nnsd number\nwill print A(number)\n"); <BR>
return -1; <BR> } <BR> Target.buff_len =
Target.repr_len = strlen(argv[1]); <BR> Target.repr_str = (char
*)malloc(Target.buff_len); <BR> for (i = 0; i<Target.repr_len;
i++) <BR> Target.repr_str[Target.repr_len-i-1] =
argv[1][i] - '0'; <BR> printStrNumber(&Target); <BR>
<P> // set sequence pointer to 0 <BR>
makeZeroStrNumber(&N); <BR>
<P> initSubSets(); <BR> short index, index_N,
min_A_index; <BR> unsigned long progress_cntr = 0; <BR>
do <BR> { <BR> increment(&N);
<BR> index_N = getSubsetIndex(&N); <BR>
if (index_N == 0x3FF) // if the nuber has all 10 digits
double <BR>nothing <BR> { <BR>
min_A_index = 0x3FF; <BR>
break; <BR> } <BR>
min_A_index = 0; <BR>
<P> // find smallest of possible candidates:
<BR> for(i = 1; i<trellis_len[index_N]; i++)
<BR> { <BR>
if(firstGreaterThanSecond( <BR>
subset_top+min_A_index, <BR>subset_top+trellis[index_N][i])) <BR>
min_A_index =
trellis[index_N][i]; <BR> } <BR>
if (!firstGreaterThanSecond(&Target, &N)) // That's our number!
<BR> break; <BR>
<P> if (!(progress_cntr++ & 0xFFFFF)) //report
progress <BR> { <BR>
printf("\nCurrent n:\n"); <BR>
printStrNumber(&N); <BR>
printf("Current A(n):\n"); <BR>
printStrNumber(subset_top+min_A_index); <BR> } <BR>
<P> findNextInSubset(min_A_index); <BR>
} <BR> while(true); <BR>
<P> printf("\n\n***********\nFinal sequence index n:\n");
<BR> printStrNumber(&N); <BR> printf("Sequence
member A(n):\n"); <BR> printStrNumber(subset_top+min_A_index); <BR>
<P>
<DIV class=qt id=qhide_984586 style="DISPLAY: block">} <BR><BR></DIV>void
initSubSets() <BR>{ <BR> short i, j, k; <BR>
<P> // Take separate care of subsets {} {0} and {0123456789}
<BR> makeZeroStrNumber(subset_top+0); <BR>
subset_top[0].repr_len = 0x7FFFFFFFL; <BR>
makeZeroStrNumber(subset_top+1); <BR> subset_top[1].repr_len =
0x7FFFFFFEL; <BR> makeZeroStrNumber(subset_top+0x3FF); <BR>
<P> for (i = 2; i<0x3FF; i++) <BR> { <BR>
printf ("\nInitializing subset 0x%x\n", i); <BR>
trellis_len[i] = 0x400; <BR> for
(j=0; j<10; j++) <BR> if ((0x1
<< j) & i) <BR>
trellis_len[i] >>=1; <BR>
<P> trellis[i] = (short *)
malloc(trellis_len[i]*sizeof(short)); <BR> for (j= k=
0; j<0x400; j++) <BR> if (!(j &
i)) <BR> trellis[i][k++]
=j; // pointer to mating subset <BR>
<P> makeZeroStrNumber(subset_top+i); <BR>
findNextInSubset(i); <BR> printf
("Trellis length: %x\n", trellis_len[i]); <BR>
printStrNumber(subset_top+i); <BR> } <BR>
<P>
<DIV class=qt id=qhide_984587 style="DISPLAY: block">} <BR><BR></DIV>void
increment(StrNumber* n) <BR>{ <BR> bool carryover; <BR>
long dec_pos = 0; <BR> char digit; <BR>
<P> do <BR> { <BR>
carryover = 0; <BR> digit = n->repr_str[dec_pos];
<BR> if(++digit == 10) <BR>
{ digit = 0; carryover = true; } <BR>
n->repr_str[dec_pos] = digit; <BR> if
(carryover) <BR> if (++dec_pos ==
n->repr_len) <BR>
addMSDigit(n); <BR> } <BR> while (carryover); // try
next more significant digit <BR>
<P>
<DIV class=qt id=qhide_984588 style="DISPLAY: block">} <BR><BR></DIV>void
findNextInSubset(short index) <BR>{ <BR> bool carryover; <BR>
long dec_pos = 0; <BR> char digit; <BR>
<P> if (index == 0x0) return; // empty subset <BR> if
(index == 0x1) return; // zeros only <BR>
<P> do <BR> { <BR> do <BR> {
<BR> carryover = 0; <BR>
digit = subset_top[index].repr_str[dec_pos]; <BR> do
<BR> { <BR>
if(++digit == 10) <BR> { digit = 0;
carryover = true; } <BR> } <BR>
while (!(index & (0x1 << digit))); <BR>
subset_top[index].repr_str[dec_pos] = digit; <BR>
if (carryover) <BR> if (++dec_pos ==
subset_top[index].repr_len) <BR>
addMSDigit(subset_top+index); <BR> } <BR> while
(carryover); // try next more significant digit <BR> dec_pos = 0;
<BR> } <BR> while (getSubsetIndex(subset_top+index) !=
index); <BR>
<P>
<DIV class=qt id=qhide_984589 style="DISPLAY: block">} <BR><BR></DIV>bool
firstGreaterThanSecond(StrNumber* n1, StrNumber* n2) <BR>{ <BR> if
(n1->repr_len != n2->repr_len) <BR> return
n1->repr_len > n2->repr_len; <BR>
<P> long len = n1->repr_len; <BR> long i;
<BR> for (i=len-1; i>=0; i--) <BR> if
(n1->repr_str[i] != n2->repr_str[i]) <BR>
return n1->repr_str[i] > n2->repr_str[i]; <BR>
return false; // they are equal; should never happen <BR>
<P>
<DIV class=qt id=qhide_984590 style="DISPLAY: block">} <BR><BR></DIV>void
addMSDigit(StrNumber* n) <BR>{ <BR> n->repr_len++; <BR>
if (n->repr_len > n->buff_len) <BR> { <BR>
long new_bufflen = 2* n->buff_len; <BR>
char *new_buffer = (char *)malloc(new_bufflen); <BR>
for (long i = 0; i<n->buff_len; i++) <BR>
new_buffer[i] = n->repr_str[i]; <BR>
free(n->repr_str); <BR>
n->repr_str = new_buffer; <BR> n->buff_len =
new_bufflen; <BR> } <BR>
n->repr_str[n->repr_len-1] = 0; <BR>
<P>
<DIV class=qt id=qhide_984591 style="DISPLAY: block">} <BR><BR></DIV>short
getSubsetIndex(StrNumber* n) <BR>{ <BR> short result = 0;
<BR> for (long i = 0; i<n->repr_len; i++)
<BR> result |= 0x1 << n->repr_str[i];
<BR> return result; <BR>
<P>
<DIV class=qt id=qhide_984592 style="DISPLAY: block">} <BR><BR></DIV>void
makeZeroStrNumber(StrNumber* n) <BR>{ <BR> n->buff_len = 0x10;
<BR> n->repr_str = (char *)malloc(n->buff_len); <BR>
n->repr_len = 1; <BR> n->repr_str[0] = 0; <BR>
<P>
<DIV class=qt id=qhide_984593 style="DISPLAY: block">} <BR><BR></DIV>void
printStrNumber(StrNumber* n) <BR>{ <BR> long print_len; <BR>
bool truncated = n->repr_len > 0x20; <BR> if
(truncated) <BR> print_len = 0x20; <BR>
else <BR> print_len = n->repr_len; <BR>
<P> printf("Length: %d, number: ", n->repr_len); <BR>
for (long i = 0; i < print_len; i++) <BR>
printf("%d", n->repr_str[n->repr_len -i -1]); <BR> if
(truncated) <BR> printf("...\n"); <BR>
else <BR> printf("\n");
<BR></P></FONT></DIV></BODY></HTML>