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