increasing comma sequences of positive integers
Olivier Gerard
ogerard at ext.jussieu.fr
Tue Dec 11 19:58:03 CET 2007
(Forwarded from David Wilson)
Every positive integer n has at most one comma sequence predecessor p(n),
that is, a number which may precede it in a comma sequence. p(n) is
defined for all positive integers except for the 50 integers in the
following set
S = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
13, 14, 15, 16, 17, 18, 19, 20, 21, 25,
26, 27, 28, 29, 30, 31, 32, 37, 38, 39,
40, 41, 42, 43, 49, 50, 51, 52, 53, 54,
62, 63, 64, 65, 74, 75, 76, 86, 87, 98
}
p(n) is undefined for n in S, for all other n in N, p(n) < n.
Starting with any positive integer n, we can iterate p on n until we
reach a unique element a(n) in S, called the ancestor of n.
Going forward, most positive integers n have a unique successor n.
However, there are a smattering of integers that have no successor,
specifically, the integers in the set
T = { (10^x + 9y) - 100 : x >= 2 and 2 <= y <= 9 }
That is
T = {
18, 27, 36, 45, 54, 63, 72, 81,
918, 927, 936, 945, 954, 963, 972, 981,
9918, 9927, 9936, 9945, 9954, 9963, 9972, 9981,
...
}
If a comma sequence reaches an element of T, the sequence ends there.
There is also a sparse set of integers that have two successors, these
form the strangely similar set
B = { (10^x + 9)y - 100 ; x >= 2 and 2 <= y <= 9 }
or
B = {
118, 227, 336, 445, 554, 663, 772, 881,
1918, 2927, 3936, 4945, 5954, 6963, 7972, 8981,
19918, 29927, 39936, 49945, 59954, 69963, 79972, 89981,
...
}
(10^x + 9)y - 100 has the two successors (10^x)y - 1 and (10^x)y. No
positive integer has more than two successors.
If a comma sequence reaches an element of T, it is possible to continue
the sequence in two ways from that element.
You will notice that comma sequence terminating and branching elements
all occur just before (within 100 of) an initial digit change. On intervals
where the initial digit of its elements remains constant, however, a comma
sequence behaves very nicely, with periodic first differences. This allows
one to do some modular magic to skip over these intervals in constant time,
which allows us to quickly compute a(n) for very large n.
Using this knowledge, I wrote a program to compute m(n), the largest
possible element in a comma sequence starting with n, for n in S. It turns
out that there are infinite comma sequences starting with 20, a comma
sequence with any other start value in S terminates at or before 10^365-82.
n m(n)
1 10^25-28
2 10^16-82
3 10^2-64
4 10^7-55
5 10^16-64
6 10^42-64
7 10^3-64
8 10^13-28
9 10^24-19
10 10^13-19
13 10^87-37
14 10^11-82
15 10^2-28
16 10^14-55
17 10^54-55
18 10^2-82
19 10^6-19
20 Infinity
21 10^5-19
25 10^4-37
26 10^7-28
27 10^2-73
28 10^4-73
29 10^8-64
30 10^365-82
31 10^2-55
32 10^9-82
37 10^4-82
38 10^17-37
39 10^3-82
40 10^30-82
41 10^3-46
42 10^5-73
43 10^2-19
49 10^4-55
50 10^18-73
51 10^18-55
52 10^21-19
53 10^3-28
54 10^2-46
62 10^7-19
63 10^2-37
64 10^132-19
65 10^5-37
74 10^3-55
75 10^5-46
76 10^24-46
86 10^5-82
87 10^12-82
98 10^4-64
hv at crypt.org wrote:
:%S A000001 1,1,5,43,875,49506
Bother, my crude code was cruder than I had realised: both the last two
terms are wrong. Corrected terms shown in the copy below. I'm not sure
how I'd go about calculating a(7), I'd welcome thoughts on that.
%I A000001
%S A000001 1,1,5,43,876,49511
%N A000001 The number of multisets A={a_1,a_2,...a_n} such that prod{1+1/a_i}=2
%e A000001 The multiset A={3,3,8} has prod{1+1/a_i}=4/3*4/3*9/8=2; a(3)=5 because there are 5 such sets with 3 elements (the others being {2,4,15}, {2,5,9}, {2,6,7}, {3,4,5})
%C A000001 For given n, the largest element appears in the set {2, 4, 16, 256, ... 2^2^(n-2), 2^2^(n-1)-1}
%C A000001 If k is in A, then there are tau(k(k+1))/2 possible n+1-element sets {A-k \union {k+x, k+y}} that also have the property, where xy=k(k+1)
%K A000001 nonn,more,new
%O A000001 1,3
%Y A000001 Cf. A002966, the parallel sequence for sum{1/a_i}=1
%A A000001 Hugo van der Sanden (hv at crypt.org)
:I'd welcome confirmation of the last term, and more terms: I don't have
:time to do more with this right now.
:
:Inspired by an aside in A066218, this actually originated as: find n such
:that 2 tau(n) = sum_{d | n} tau(d); these multisets are the powers+1 in
:the prime factorisation of any such n.
:
:This seems like quite an interesting set to investigate further: it is not
:surprising that it has parallels with sum{1/a_i}=1, such as that hinted
:at in the second comment (parallel to (tau(k^2)+1)/2 in the sum case).
:
:The sets contributing to a(1)..a(4) are:
:
:<1> ; <2 3> ; <2 4 15> <2 5 9> <2 6 7> <3 3 8> <3 4 5> ;
:<2 4 16 255> <2 4 17 135> <2 4 18 95> <2 4 19 75> <2 4 20 63> <2 4 21 55>
:<2 4 23 45> <2 4 25 39> <2 4 27 35> <2 4 30 31> <2 5 10 99> <2 5 11 54>
:<2 5 12 39> <2 5 14 27> <2 5 15 24> <2 5 18 19> <2 6 8 63> <2 6 9 35>
:<2 6 11 21> <2 6 14 15> <2 7 7 48> <2 7 8 27> <2 7 9 20> <2 7 12 13>
:<2 8 9 15> <2 9 10 11> <3 3 9 80> <3 3 10 44> <3 3 11 32> <3 3 12 26>
:<3 3 14 20> <3 3 16 17> <3 4 6 35> <3 4 7 20> <3 4 8 15> <3 4 10 11>
:<3 5 5 24> <3 5 6 14> <3 5 8 9> <3 6 7 8> <4 4 5 15> <4 5 5 9> <4 5 6 7>
:
:.. and I'd include them in a sequence of their own if I could think of
:a useful way to arrange it. (The original 2tau(n) interpretation may
:also be worth submitting.)
:
:Hugo
"Compact" here means the smallest difference between terms. One candidate is
A052548: 3, 4, 6, 10, 18, etc. It is easy to show that there is one prime
between successive members of this sequence by application of Bertrand's
Postulate (at least one prime between n and 2n - 2, n >=3):
3, 3*2 - 2 = 4
4, 4*2 - 2 = 6
6, 6*2 - 2 = 10
etc.
Are there any sequences more "compact" than this that can be proved to have
primes between successive members?
More information about the SeqFan
mailing list