A good algorithm for A094348?

[Peter Luschny]

A094348 is a very interesting sequence as I recently noted.
There is probably some important relation to J. C. Lagarias,
'An elementary problem equivalent to the Riemann hypothesis'.

It would be nice to have a b-file for this sequence, which means
a list of the first 1000 or 10000 members of this sequence.

Probably the problem is not very hard. Any ideas for an
algorithm would be greatly appreciated.

[Sonia Keys]

Hello and thank you for the invitation, Peter. It all looks like
interesting work, although I'm not sure my math skills will allow me
to contribute very much. For this problem, for example, I don't see
an algorithm yet.

If I understand the description, n = f(j, k) makes a triangle, but the
elements of the triangle are not unique, and not in sequence order.
Also, there are combinations to try for solving each n = f(j, k)?
Ugh!

Sonia

On Nov 23, 2:59 pm, Peter Luschny <peter.lusc...@googlemail.com>
wrote:

[Peter Luschny]

On 25 Nov., 05:49, Sonia Keys wrote:

> Hello and thank you for the invitation, Peter.

Welcome Sonia!

> It all looks like interesting work, although I'm not sure
> my math skills will allow me to contribute very much.

Well, have you seen that Bill Thurston today joined the OeisWiki?
One of the greatest mathematicians alive! Perhaps I should invite
him also :)?

> For this problem, for example, I don't see an algorithm yet.
> If I understand the description, n = f(j, k) makes a triangle, but the
> elements of the triangle are not unique, and not in sequence order.
> Also, there are combinations to try for solving each n = f(j, k)?
> Ugh!

Yes, it is not straightforward. Matt commented:

MV: I think I can best explain the sequence by
MV: referring to sequence A096179: "Triangle read
MV: by rows: T(n,k) is the smallest positive integer
MV: having at least k of the first n positive integers
MV: as divisors."
MV: The triangle begins:
MV: 1
MV: 1 2
MV: 1 2 6
MV: 1 2 4 12
MV: 1 2 4 12 60
MV: 1 2 4 6 12 60
MV: I'll do row 6 as an example. Of the integers from
MV: 1 through 6, obviously 1 is the first positive
MV: integer with at least 1 of them as a divisor
MV: (the first column is all 1s, for obvious reasons).
MV: 2 is the first with at least 2 of those 6 numbers
MV: as divisors (1 and 2); 4, the first with at
MV: least 3 (1, 2 and 4); 6, the first to have
MV: 4 (1, 2, 3 and 6); 12, the first to have
MV: 5 (1, 2, 3, 4 and 6); and A003418(6)=60
MV: is the first to have all 6.

David Wasserman proposed the following approach
- if I understand his code right:
Observe that A096179 is a sub sequence of A025487.
Now scan through A025487 and test if the constrains
of A096179 hold. This looks promising; the details
I have yet to understand, though.

Peter

[Psychedelic Geometry]

This is an observation, maybe useless, about this sequence:

A000005(A094348(n+1))>=A000005(A094348(n)) this hold for the known
terms of the sequence:

DivisorSigma[0, #] & /@ {1, 2, 4, 6, 12, 24, 36, 48, 60, 72, 120, 180,
240, 360, 420, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080,
15120, 20160, 25200, 27720, 30240, 45360, 50400, 55440, 83160,
110880, 166320, 221760, 277200, 332640, 360360, 498960, 554400,
665280, 720720}

{1, 2, 3, 4, 6, 8, 9, 10, 12, 12, 16, 18, 20, 24, 24, 30, 32, 36, 40,
\
48, 60, 64, 72, 80, 84, 90, 96, 96, 100, 108, 120, 128, 144, 160, \
168, 180, 192, 192, 200, 216, 224, 240}

[Peter Luschny]

On 1 Dez., 00:33, Psychedelic Geometry wrote:
> This is an observation, maybe useless, about this sequence:
> A000005(A094348(n+1))>=A000005(A094348(n)) this hold for the known
> terms of the sequence:

I do not think that this is useless. At the moment I believe
we need two things: (1) A fast way to generate A025487
(2) a filter which reduces A025487 to A094348.
A first numerical test indicates that your observation might
very well point to such a filter.

seq([i,member(i,A094348),tau(i)],i=A025487);
[1,true,1], [2,true,2], [4,true,3], [6,true,4], [8,false,
4],
[12,true,6], [16,false,5], [24,true,8], [30,false,8],
[32,false,6],
[36,true,9], [48,true,10], [60,true,12], [64,false,7], [72,true,
12],
[96,false,12], [120,true,16], [128,false,8], [144,false,15],
[180,true,18], [192,false,14], [210,false,16], [216,false,16],
[240,true,20], [256,false,9], [288,false,18], [360,true,24],
[384,false,16], [420,true,24], [432,false,20], [480,false,24],
[512,false,10], [576,false,21], [720,true,30], [768,false,18],
[840,true,32], [864,false,24], [900,false,27], [960,false,28],
[1024,false,11],[1080,false,32],[1152,false,24],[1260,true,36],
[1296,false,25],[1440,false,36],[1536,false,20],[1680,true,40],
[1728,false,28],[1800,false,36],[1920,false,32],[2048,false,12],
[2160,false,40],[2304,false,27],[2310,false,32]

[ghod...@comcast.net]

On 1 Dez., 00:33, Psychedelic Geometry wrote:
> This is an observation, maybe useless, about this sequence:
> A000005(A094348(n+1))>=A000005(A094348(n)) this hold for the known
> terms of the sequence:

You're not alone in noticing this (see conjecture under http://oeis.org/A140999). 5354228880 is a counterexample, however (though perhaps not the smallest). As the smallest multiple of the first 23 positive integers, it belongs to A094348, but has only 1920 divisors, and a smaller member of A002182 has 2016.  

A002182(74) = 4655 851200 = 2 ^ 6 x 3 ^ 2 x 5 ^ 2 x 7 x 11 x 13 x 17 x 19 
Number of divisors:  2016
A003418(23) = 5354 228880 = 2 ^ 4 x 3 ^ 2 x 5 x 7 x 11 x 13 x 17 x 19 x 23
Number of divisors:  1920 (Source: http://www.alpertron.com.ar/ECM.HTM)

All members of http://oeis.org/A002182 and http://oeis.org/A003418  belong to A094348.  A003418(23) is just the first member of A003418 to have fewer divisors than some smaller member of A002182. But I suspect that they all do except for a finite number of exceptions.  The intersection of A2182 and A3418 has definitely been proved finite; see http://oeis.org/A055492, http://oeis.org/A095921.

http://oeis.org/A164377 shows the A094348 members that are not in A002182.

Thanks for your interest, everybody, and good luck - I wish I could be more help.

Best regards,
Matt Vandermast

 

[M. Hasler]

> MV: I think I can best explain the sequence by
> MV: referring to sequence A096179: "Triangle read
> MV: by rows: T(n,k) is the smallest positive integer
> MV: having at least k of the first n positive integers
> MV: as divisors."

Yes, I think this is a good approach to /explain/ (but maybe not
calculate) the sequence.
In any case, the definition of A094348 should be clarified a bit.
By "smallest positive multiple of..." they mean the "LCM (least /
common/ multiple) of ..." ?
and the j numbers must of course all be different.

But the sequence A096179 can be easily computed:
A096179(k,j)={ my(m=lcm(vector(j,i,i))); forvec(v=vector(j,i,[1,k]),
m>lcm(v) & m=lcm(v),2); m }

Probably one could make it more intelligent, e.g. using rules like
"among the numbers [1..k] to use, avoid the largest primes (and
numbers with large (thus few) prime factors)".

The problem for A094348 is that we don't know up to which k we have to
go.

Well, unless we think about it...

Maximilian

[ghod...@comcast.net]

Thanks for the comments. I don't see any ambiguity in the definition at this time, however. I hope the A094348 example helps: 

72 is a multiple of seven of the first nine positive integers (namely, 1, 2, 3, 4, 6, 8 and 9). It is the smallest positive integer for which this is true.

So 72 is the "smallest positive multiple" of the numbers listed.  The word "positive" is of course necessary to eliminate the negative numbers.  Maybe there's a problem I'm not seeing, but I think the phrase should not be changed unless there's definitely a problem. 

My concern is that if the phrase "least common multiple" is used, people will have a harder time understanding the sequence, because in ordinary use "least common multiple" means the number is divisible by *all* of the numbers in a certain set.  In other words, the phrase may cause some readers to have a harder time getting their mind around the idea that the LCM of at least j of the first k positive integers need not be a multiple of A003418(k).  

Best regards,
Matt Vandermast 

[Peter Luschny]

Dear Matt,

please do not change the subject when answering to a message.
The name of this thread is "A good algorithm for A094348"
and there is no need to change it to something like

"[seqcomp:17] Re: A good algorithm for A094348?"

Or has this been done by your software?

And a second request: There is no need to append the message
of the preceding contributor to your answer. It will always
be clear and immutable to what you are answering. So this
is a only a waste of resources with no benefit.

Thanks for your cooperation!
Cheers, Peter

[Sonia Keys]

I have in mind an algorithm for A094348. Actually I've been sitting
on it for a week or so, thinking I would code it up, but that hasn't
happened yet, so I thought I would share my ideas.

In the triangle of A096179, there is one more sequence I'll identify
with parentheses

(1)
1 (2)
1 2 6
1 2 (4) 12

1 2 4 12 60

1 2 4 (6) (12) 60
1 2 4 6 12 60 420
1 2 4 6 12 24 120 | 840
1 2 4 6 12 24 72 | 360 2520
1 2 4 6 12 24 60 | 120 360 2520
1 2 4 6 12 24 60 | 120 360 2520 27720
1 2 4 6 12 (12) (24) | 60 120 360 ? 27720

This is A061799, smallest number with at least n divisors. There is a
term of A061799 in each column of the triangle. Below these terms,
the numbers are all the same and don't need to be recomputed.

Further, since values never decrease to the right in a row, and never
increase down in a column, A061799 can be used to terminate the
processing. We compute by columns, and down within each column. In
the example above, once we have reached A061799(7) = 24 in column 7,
row 12, we know that we have computed all values of A094348 <= 24. We
have not computed any values from columns > 7 (the right of the line)
and we know we have all values of A094348 <= 24.

To compute the values of the triangle efficiently, information from
each column can be used to compute the next column. The number in the
triangle is the "smallest positive multiple..." but if we keep all of
the positive multiples, then we can use these to generate positive
multiples to consider for the next column.

I have some ideas for implementing all of this, but of course methods
will vary with the programming language or software used.

Sonia

[Peter Luschny]

Hi Sonia,

> This is A061799, smallest number with at least n divisors.  There is a
> term of A061799 in each column of the triangle.  Below these terms,
> the numbers are all the same and don't need to be recomputed.
> Further, since values never decrease to the right in a row, and never
> increase down in a column, A061799 can be used to terminate the
> processing.  We compute by columns, and down within each column.  In
> the example above, once we have reached A061799(7) = 24 in column 7,
> row 12, we know that we have computed all values of A094348 <= 24.  We
> have not computed any values from columns > 7 (the right of the line)
> and we know we have all values of A094348 <= 24.

Nice idea. First let me give a slightly larger table.

[1] 1
[2] 1 2
[3] 1 2 6
[4] 1 2 4 12
[5] 1 2 4 12 60
[6] 1 2 4 6 12 60
[7] 1 2 4 6 12 60 420
[8] 1 2 4 6 12 24 120 840
[9] 1 2 4 6 12 24 72 360 2520
[10] 1 2 4 6 12 24 60 120 360 2520
[11] 1 2 4 6 12 24 60 120 360 2520 27720
[12] 1 2 4 6 12 12 24 60 120 360 2520 27720
[13] 1 2 4 6 12 12 24 60 120 360 2520 27720 360360
[14] 1 2 4 6 12 12 24 60 120 360 840 2520 27720 360360
[15] 1 2 4 6 12 12 24 60 60 120 360 840 2520 27720 360360
[16] 1 2 4 6 12 12 24 48 60 120 240 720 1680 5040 55440
720720
[17] 1 2 4 6 12 12 24 48 60 120 240 720 1680 5040 55440
720720 12252240
[18] 1 2 4 6 12 12 24 36 60 120 180 360 720 2520 5040
55440 720720 12252240
[19] 1 2 4 6 12 12 24 36 60 120 180 360 720 2520 5040
55440 720720 12252240 232792560
[20] 1 2 4 6 12 12 24 36 60 60 120 180 360 720 2520
5040 55440 720720 12252240 232792560
[21] 1 2 4 6 12 12 24 36 60 60 120 180 360 720 1260
2520 5040 55440 720720 12252240 232792560

[1-2-3--4--5--6---7---8---9--10---11---12----13----14----15----16------17--------18--------19-------20----------21]

I am now computing column 8. The value still is '36'.
My question is: What guarantee do I have that it will drop
eventually to 24? Maybe it stays forever '36'?

Cheers, Peter

[Sonia Keys]

On Dec 6, 10:42 am, Peter Luschny <peter.lusc...@googlemail.com>
wrote:
> ...

> I am now computing column 8. The value still is '36'.
> My question is: What guarantee do I have that it will drop
> eventually to 24? Maybe it stays forever '36'?

Hi Peter,

It's the definition of A061799 and the definition of our triangle.
Column 8 is numbers obtained by multiplying 8 numbers, and A061799(8)
is by definition the smallest number with at least 8 divisors. The 8
numbers are {1,2,3,4,6,8,12,24} so the number will fall to 24 on row
24.

Hmm...ok, so, in general, the number won't fall to A061799(n) until
row A061799(n). I guess that's way too many to compute, and it looks
kind of pointless to compute all those 36s when you know nothing's
going to happen until row 24. Maybe there is a way to use the
factorization of A061799(n) to determine which rows of column(n) are
worth computing.

[Peter Luschny]

Hi Sonja!

> Maybe there is a way to use the
> factorization of A061799(n) to determine which rows of column(n) are
> worth computing.

Yes, I think the prime-factorization is the only way to a more
efficient algorithm. To the OEIS I just submitted a row-based
solution for Maple.

a096179_row := proc(n) local k,L,l,R,LCM,comb;
R := NULL; LCM := ilcm(seq(i,i=[$1..n]));
for k from 1 to n-1 do
L := LCM;
comb := iterstructs(Combination(n),size=k):
while not finished(comb) do
l := nextstruct(comb); print(l);
L := min(L,ilcm(op(l)));
od;
R := R,L;
od;
R,LCM end:

Say n=5, then the combinations are computed, then the lcm of them and
the
minimum taken. Very simple and readable, however with complexity 2^n
(per row n).

{1}{2}{3}{4}{5}
{1,2}{1,3}{1,4}{1,5}{2,3}{2,4}{2,5}{3,4}{3,5}{4,5}
{1,2,3}{1,2,4}{1,2,5}{1,3,4}{1,3,5}{1,4,5}{2,3,4}{2,3,5}{2,4,5}{3,4,5}
{1,2,3,4}{1,2,3,5}{1,2,4,5}{1,3,4,5}{2,3,4,5}
{1,2,3,4,5}

A096179 is a very natural generalization of the lcm{1,2,3,...,n}
and I am surprised to have seen virtually nothing about this sequence
in the literature.

After all we are talking about the second Chebyshev function
which is considered as the mathematical version of the
pi (prime counting) function.

Thus we see the connection to A094348 and Riemann, which was
the starting point of this thread.

Cheers, Peter

[Psychedelic Geometry]

This is my first try of Mathematica code for A096179:
----------------------------------------------------
(* Triangle *)
A096179[n_,k_]:=Min[LCM@@@Subsets[Range[n],{k}]];

(* Linear *)
A002260[n_]:=n-Binomial[Floor[1/2+Sqrt[2*n]],2];
A002024[n_]:=Floor[1/2+Sqrt[2*n]];
A096179[n_]:=A096179[n]=A096179[A002024[n],A002260[n]]

(* Help *)
A002024::usage="A002024: n appears n times.";
A002260::usage="A002260: Integers 1 to k followed by integers 1 to k+1
etc. (a fractal sequence).";
A096179::usage="A096179: Triangle read by rows: T(n,k) is the smallest
positive integer having at least k of the first n positive integers as
divisors.";
------------------------------------------------
This code seems to be very slow and uses a lot of memory, but I just
want to point the main idea out, the use of the subsets with exactly k
elements of the powerset of the range {1,2,..n}, I´ll try to find a
recursive relation for the sequence.


Here there are the first 300 terms of A096179:

{1,1,2,1,2,6,1,2,4,12,1,2,4,12,60,1,2,4,6,12,60,1,2,4,6,12,60,420,1,2,4,6,12,24,120,840,1,2,4,6,12,24,72,360,2520,1,2,4,6,12,24,60,120,360,2520,1,2,4,6,12,24,60,120,360,2520,27720,1,2,4,6,12,12,24,60,120,360,2520,27720,1,2,4,6,12,12,24,60,120,360,2520,27720,360360,1,2,4,6,12,12,24,60,120,360,840,2520,27720,360360,1,2,4,6,12,12,24,60,60,120,360,840,2520,27720,360360,1,2,4,6,12,12,24,48,60,120,240,720,1680,5040,55440,720720,1,2,4,6,12,12,24,48,60,120,240,720,1680,5040,55440,720720,12252240,1,2,4,6,12,12,24,36,60,120,180,360,720,2520,5040,55440,720720,12252240,1,2,4,6,12,12,24,36,60,120,180,360,720,2520,5040,55440,720720,12252240,232792560,1,2,4,6,12,12,24,36,60,60,120,180,360,720,2520,5040,55440,720720,12252240,232792560,1,2,4,6,12,12,24,36,60,60,120,180,360,720,1260,2520,5040,55440,720720,12252240,232792560,1,2,4,6,12,12,24,36,60,60,120,180,360,720,1260,2520,5040,27720,55440,720720,12252240,232792560,1,2,4,6,12,12,24,36,60,60,120,180,360,720,1260,2520,5040,27720,55440,720720,12252240,232792560,5354228880,1,2,4,6,12,12,24,24,48,60,120,120,240,360,720,1680,2520,5040,27720,55440,720720,12252240,232792560,5354228880}

Best Regards, Enrique.

[Peter Luschny]

Hi Enrique,

the nice thing is that I can learn Mathematica /en passant/
reading your code.

> This is my first try of Mathematica code for A096179:

> A096179[n_,k_]:=Min[LCM@@@Subsets[Range[n],{k}]];

This is really terse, here Mathematica shines. Now I only have
to find out why there are three '@' and not two or four :).

The algorithm you describe is exactly the one I gave in my last post.
>> comb := iterstructs(Combination(n),size=k):

I hope you will add your piece of code to A096179. Then there
will be three very different styles: Your professional looking
Mathematica code, my pedestrian Pascal-like Maple code and
Maximilians hackerish Pari code ;-) Who throws in some Sage/Phyton?

> This code seems to be very slow and uses a lot of memory,

Could you be please be more explicit what 'slow' here means?
The first 300 terms of the sequence correspond to rows 1-25.
On my PC vintage 2005 with Maple V Rel 5 (1998) this took
1 and 3/4 hours. Memory was not a limiting factor, Maple used
less then 2 MB although 836 MB were available for the process.

Back to the sequence. The most significant row until now is
row number 9.

1, 2, 4, 6, 12, 24, 72, 360, 2520

Here '72' appears and only here. An important warning that we
cannot hope that things turn out to be easy, I think. Or am I wrong?
Matt once told me that noticing that 72 deserved to be part of
the sequence was an important step for him to realize that this
sequence is worthy of recognition.

Cheers, Peter

[M. Hasler]

There is also a 1-line version for Maple:

A096179:=(n,k)-
>min(seq(`if`(nops(s)=k,lcm(op(s)),NULL),s=combinat[powerset](n)));

Just for information, on my laptop (vintage 2005, too) my PARI code
prints the first 300 terms in about 50 seconds...

Note that rather to consider all subsets of k elements of {1...n} it
considers subsets of k-1 elements of {2...n},
since the "1" will always be part of the "minimal" subset.
I think we could also suppose that the 2 is always part of the set
(for n>1).
If one wants to produce "promising" sets with low lcm, it appears
obvious that large primes close to n should be excluded first from
the possible choices. The numbers 1...n should be reordered by their
largest prime factor to a vector v[1]...v[n],
and from the starting value of lcm(v[1]...v[k]) it can be seen which
of the numbers listed last can safely be ignored.

Maximilian

[Peter Luschny]

> 2010/12/8 M. Hasler

> There is also a 1-line version for Maple:
> A096179:=(n,k)->min(seq(`if`(nops(s)=k,lcm(op(s)),NULL),s=combinat[powerset](n)));

Brilliant! However this way does not work with older Maple versions,
not with Maple V.

Error, (in combinat/powerset/set) object too large

Well, it works, but for small n only, rows <= 16. The reason is that
in
the older combinat packages the objects were not computed on
demand and the main memory in 1998 was not very large.
Therefore this build-in limit. Later they removed many of these
limits.

> Just for information, on my laptop (vintage 2005, too) my PARI code
> prints the first 300 terms in about 50 seconds...

Wow! What Maple version do you use? Is it time for me to upgrade? :)

> Note that rather to consider all subsets of k elements of {1...n} it
> considers subsets of k-1 elements of {2...n},
> since the "1" will always be part of the "minimal" subset.
> I think we could also suppose that the 2 is always part of the set (for n>1).
> If one wants to produce "promising" sets with low lcm, it appears
> obvious that large primes close to n should be excluded first from
> the possible choices. The numbers 1...n should be reordered by their
> largest prime factor to a vector v[1]...v[n],
> and from the starting value of lcm(v[1]...v[k]) it can be seen which
> of the numbers listed last can safely be ignored.

Very nice.

Tomorrow I will report on some sequences I submitted today
inspired by the code line

iterstructs(combination(n),size=k):

What, I wondered, will happen, if I just replace 'combination'
by 'composition' or 'partition', everything else unchanged?

Peter

[M. Hasler]

> > There is also a 1-line version for Maple:
> > A096179:=(n,k)->min(seq(`if`(nops(s)=k,lcm(op(s)),NULL),s=combinat[powerset](n)));
>
> Brilliant! However this way does not work with older Maple versions,
> not with Maple V.
>
>     Error, (in combinat/powerset/set) object too large
>
> Well, it works, but for small n only, rows <= 16.

oh, that's all I tested --
Me too, I use still a somehow obsolete Maple version (7) :( !

> > Just for information, on my laptop (vintage 2005, too) my PARI code
> > prints the first 300 terms in about 50 seconds...
>
> Wow! What Maple version do you use? Is it time for me to upgrade? :)

I said *PARI* code !
The maple code takes a minute or so for n=1..13, IIRC.

Maximilian

[Psychedelic Geometry]

Hi, Peter:

Mathematica calculates the first 300 terms in less than 5 minutes, my
computer is an ASUS "potato" laptop also from 2005.
If you try to go up to the 310th term, Mathematica shows the following
funny message:

No more memory available.
Mathematica kernel has shut down.
Try quitting other applications and then retry.

And then all data in memory are lost.

The problem is that the subsets function eats the memory up, so I said
that this was my first try because now is when I turn to PARI/GP, or I
look for an alternative code to avoid the subsets function.

The reason why you need to use three @ is because sometimes Mathematica
´s functional programming is elegant but tricky:

The LCM function wants the data like this: LCM[a,b,...,n] It does not
uses lists but parameters, and the Subsets function gives its return
like that: {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1,
4, 5}, {2,
3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}} (It´s a list of vectors, or
a list of lists).

If they had coded the LCM in a different way you only should Apply the
LCM to the Subsets directly, using the shorthand version of Apply, @@,
but then LCM can not reach the inner level of the double list so you
need to fed the LCM function setting the level specification parameter
to 1, and this can be shorthanded like this:

f@@@expr is equivalent to Apply[f,expr,{1}].

http://reference.wolfram.com/mathematica/ref/Apply.html

[Peter Luschny]

> I said *PARI* code !

Yes, Maximilian, I am still in a state of shock.

[PL] Maple VR5, 1 and 3/4 hours
[MH] Pari, 50 sec.

I have gathered what we have so far:
http://www.luschny.de/math/seq/miis/MIIS096179.html

Let me remind of the real goal: The first 1000 terms of *A094348*.

Maximilian, how long does this take on your computer? :)
Ey, and just because you're at it, don't forget the b-file ;-))

Cheers, Peter

[Psychedelic Geometry]

Hello, Peter and all seqcomp members:

http://www.luschny.de/math/seq/miis/MIIS096179.html

Please note that the inline comments in PARI/GP are done with \\
instead of #

I´m now calculating the bFile for A096179 using M.F. Hasler code with:

..................................

\\ Generate all the combinations of { 1, ..., n } of length k,
\\ compute their least common multiple and choose the smallest one.

T(n, k) =
{
my(m = lcm(vector(k, i, i)));
forvec(v = vector(k-1, i, [2, n]), m > lcm(v) & m = lcm(v), 2);
m
}

A002024(n)=floor(1/2+sqrt(2*n));
A002260(n)=-binomial(A002024(n), 2)+n;
A096179(n)=T(A002024(n), A002260(n));


\\ Test for n = 1, 2, ..., 22:
\l b068559.txt
for(n = 1, 2000, print(n" "A096179(n)))

....................................................

Tomorrow we will see... maybe 2000 terms are too much, but PARI is a
low level software very nice coded and that´s because it is so fast.


More things:


1) The rows in the triangle A096179, hold for the following property:

A096179(n+1,k)>=2*A096179(n,k)

This is because, when a new element is added to the subsets: or the
LCM remains unchanged, or it is increased by some factor, and in that
case 2 is the least prime factor.
A094348 also seem to hold for A094348(n+1)<=2*A094348(n)

2) Other idea I´m following, it is to generalize the formula for
A096179(n,n)=A003418(n), to all the A096179 triangle.

http://oeis.org/A003418

a(n)=product_{p^(floor(log n/log p))}, where p runs through primes not
exceeding n (i.e. primes 2 through A007917(n)). - Lekraj Beedassy
(blekraj(AT)yahoo.com), Jul 27 2004

This formula seems to have some relation with the Legendre´s formula
for the exponent of p in the prime factorization of n!
http://psychedelic-geometry.blogspot.com/2009/12/notes-on-legendres-formula.html

Read you soon!

[Peter Luschny]

> Please note that the inline comments in PARI/GP are done with \\
> instead of #

Thanks, corrected.

> 2) Other idea I´m following, it is to generalize the formula for
> A096179(n,n)=A003418(n), to all the A096179 triangle.

There is also the interesting Monthly article from Bakir Farhi.
(You can download it from the arXiv.)

> a(n)=product_{p^(floor(log n/log p))}, where p runs through primes not
> exceeding n (i.e. primes 2 through A007917(n)). - Lekraj Beedassy
> (blekraj(AT)yahoo.com), Jul 27 2004
> This formula seems to have some relation with the Legendre´s formula
> for the exponent of p in the prime factorization of n!

Yes. Because lcm(1,2,..,n) divides n!

> http://psychedelic-geometry.blogspot.com/2009/12/notes-on-legendres-f...

Cheers, Peter

[Psychedelic Geometry]

Hi, Ladies and Gentlemen:

More things about A096179:

1) Here it is the bFile for A096179 (using for one night M. F. Hasler
´s PARI/GP code)

https://sites.google.com/site/psychgeom/psychgeom/b096179.txt?attredirects=0&d=1

2) If you prefer to watch this data in a formatted Excel sheet:

https://sites.google.com/site/psychgeom/psychgeom/A096179.xls?attredirects=0&d=1

3) If A096179(n,k)=A061799(k) then A096179(n+1,k)=A061799(k), this
sequence A061799 gives de minimal LCM of a subset of k elements, this
comment, and crossrefs, are actually missing in OEIS.

4) This Mathematica code:

f[n_, r_] :=
Times @@ Table[
Prime[i - r]^Floor[N[Log[n]/Log[Prime[i - r]], 10]], {i, 1 + r,
PrimePi[n]}]

For r=0 gives the diagonal of the triangle A096179, this is A003418,
and it is Lekraj Beedassy
`s formula, for r=1 it gives the first subdiagonal, but it can not
hold for the next subdiagonals.


Bye, and I will continue thinking (under my possibilities)

[Psychedelic Geometry]

Ups I forgot to mention that the preceeding formula for r=1, SEEMS to
hold, because I have not a proof

[Peter Luschny]

On 16 Dez., 20:59, Psychedelic Geometry wrote:

> More things about A096179:
>1) Here it is the bFile for A096179

Great. OEIS b-files are at the moment closed because of
technical problems, as far as I know.

> 2) If you prefer to watch this data in a formatted Excel sheet:

Best to place it as a wiki-table or html-table on the OEIS wiki.
More such supplement pages will come and perhaps we should find
some standard form for the page name for such extensions?

http://oeis.org/wiki/Supplement_A096179
http://oeis.org/wiki/Supp_A096179
http://oeis.org/wiki/S096179

What do the valued editors think?

> 3) If A096179(n,k)=A061799(k) then A096179(n+1,k)=A061799(k)

I leave the evaluation of this relation to the inventor of
the sequence under consideration :)

---

Just in case it is overlooked by now: I was looking
for a good algorithm for A094348, not A096179 :)

Here is what I have found out in the meantime
http://oeis.org/wiki/User:Peter_Luschny/A057641A094348

Cheers, Peter

[Sonia Keys]

On Thu, Dec 16, 2010 at 2:59 PM, Psychedelic Geometry <psychg...@gmail.com> wrote:

3) If A096179(n,k)=A061799(k) then A096179(n+1,k)=A061799(k), this
sequence A061799 gives de minimal LCM of a subset of k elements

True.  This is part of what I was attempting to point out in a previous post.  It follows from the stronger statement that A096179(j, k+1) <= A096179(j, k) and the definition of A061799(j) as the minimum. 

this comment, and crossrefs, are actually missing in OEIS.

I just submitted the connection to A061799.  (It's my first OEIS contribution!)  I didn't, however, submit the inequalities T(n+1,k) <= T(n,k) (column values can only decrease or stay the same, reading down) and T(n, k+1) >= T(n, k) (row values can only increase or stay the same, reading left to right.)

I wasn't sure that monotonicity relations are generally stated.  Peter, or anyone else with significant OEISexperience, are they?  If it's fairly easy to show, as it is in these cases, do OEIS entries typically state these?

[Peter Luschny]

Hi Sonia,

> I didn't, however, submit the inequalities
> T(n+1,k) <= T(n,k) (column values can only decrease or stay the same,
> reading down) and T(n, k+1) >= T(n, k) (row values can only increase or stay
> the same, reading left to right.)

> I wasn't sure that monotonicity relations are generally stated. Peter, or
> anyone else with significant OEISexperience, are they? If it's fairly easy
> to show, as it is in these cases, do OEIS entries typically state these?

There is no rule as far as I can see. It is up to your judgment
(and of course the editors think).

In this case the monotonicity relations are basic rules governing
the sequence. Such rules, if proved and intelligible stated will
certainly help other users to understand a sequence faster.

Moreover, when I look at the definition "T(n,k) is the

smallest positive integer having at least k of the first n

positive integers as divisors" such a property is not
immediately clear.

Thus in this case I would not hesitate to add such a comment.

Cheers Peter

[Peter Luschny]

>Psychedelic Geometry wrote:
> 2) If you prefer to watch this data in a formatted Excel sheet:

I just remembered that we can also use our seqcomp website:
https://sites.google.com/site/seqcomp/seqsupp/a096179

[Peter Luschny]

> 1) Here it is the bFile for A096179 (using for one night M. F. Hasler
> ´s PARI/GP code)

So it was a one night stand?

I extracted from your table the set

1, 2, 4, 6, 12, 24, 36, 48, 60, 72, 120, 180, 240, 360, 420,

720, 840, 1260, 1680, 2520, 5040, 10080, 15120, 25200, 27720,
30240, 55440, 110880, 166320, 277200, 332640, 360360, 720720,
1441440, 2162160, 3603600, 4324320, 10810800, 12252240, 21621600,
61261200, 183783600, 232792560, 367567200, 1163962800, 3491888400,
5354228880, 6983776800, 26771144400, 80313433200, 160626866400,
2329089562800, 4658179125600, 14440355289360, 72201776446800,
144403552893600

and compared it with A094348. As you see already 7560 is not in the
set!

And this reminds me of what Maximilian said:

| "Yes, I think this is a good approach to /explain/ (but maybe not

| calculate) the sequence. The problem for A094348 is that we don't

| know up to which k we have to go."

"Well, unless we think about it... "

+1 for Maximilian.

Sadly, we have not made yet any progress with regard to the
question of the OP. Or to put it positively:

The chance to win this cup is still open :)

Cheers, Peter

[Psychedelic Geometry]

Hi, Sonia:

I read your post but I´ve did not paid enought attention to the relation with A061799 you pointed out, I apologize for that. But in the end I did the right thing because I wrote everything here before making changes in OEIS.

I´ve notice that you have not signed your comment with your name, after they have made changes in the way the comments are added to OEIS, now contributor´s name and email are not automatically appended so I decided to add them by myself in my comments.

But today I´ve seen the following...

http://oeis.org/wiki/Style_Sheet

• You are encouraged to add your name when you add something to an existing entry.
• This is not essential, since the same information is available in the History section, but it is useful for the reader who is in a hurry
• After Jan 01 2011 the OEIS policy will be not to display email addresses of contributors

"You are encouraged to add your name"... those are good news for egocentrical engineers.

Other issue you said, is how to use A061799 to speed up the calculation for A096179... with Mathematica and my little package (OEIS Package)  it is easy to use precomputed data from A061799 and  A003418, but the main code is slow, so I thought to use PARI/GP, but with PARI is very hard to read data from a bfile, because if you use the command readvec and you are loading for example:

1 1

2 2

Then you get: [11,22]  the blank are skipped and you actually read a mess. This is also a problem I would like to solve with PARI, and this would be nice to upload to OEIS, maybe an extra C function lib, I don´t know.

Other options (distinct to sloppy PARI code, that for example could split the strings or editing bfiles) are to use Mathlink (Mathematica) with PARI, or other interfaces Python PARI, but actually I don´t know how to use them.

Best Regards, Enrique.

[Psychedelic Geometry]

Hello, Peter:

Well, failure is an option, at least we have done some job for the other sequences.

So it was a one night stand?

I let the computer from maybe 1:00 till 13:00, because I went, on saturday morning, to look for some catharellus lutescens and I return home just to make a nice tortilla (omelette).

we don't  know up to which k we have to go

What if we calculate the sequence of k? (The least k)

Cheers, Enrique.

[Sonia Keys]

Enrique,

No worries about any of this...

On Sat, Dec 18, 2010 at 6:57 AM, Psychedelic Geometry <psychg...@gmail.com> wrote:

Hi, Sonia:

I read your post but I´ve did not paid enought attention to the relation with A061799 you pointed out, I apologize for that. But in the end I did the right thing because I wrote everything here before making changes in OEIS.

I´ve notice that you have not signed your comment with your name....

Being new, I tried to be conservative and make minimal changes.  It seemed that every little observation on an OEIS page wasn't always signed, so I left my name off.  I was happy to see it visible in the history.

 

Other issue you said, is how to use A061799 to speed up the calculation for A096179...

Well, mostly I was thinking of using  A061799 to speed up calculation of A094348.  In either case, as you observed, there's no point in computing anything below A061799, so there are a bunch of elements that don't have to be solved.  Unfortunately for computing A096179 though, A061799 dives down into the triangle rather steeply so before long it's not saving you that much.

For computing A094348, I thought it might be enough to compute terms above A061799, and I did eventually write this program, but it didn't get as far as I had hoped.  I could compute the triangle above A061799 only up to n=37 or so before the little computer I am using bogged down.  A061799(37) is only 1680, which pitifully is only A094348(19).  (37 out of 64 possible divisors, by the way, still isn't enough to produce 7560.)

I haven't quite given up on this approach though.  I'm trying now to cut away the upper part of the triangle as well, and leave only the narrow spike though the middle of the triangle that produces the terms of A094348 as early as possible.  Sorry I haven't got that doing anything useful yet so I have no results to announce.

with Mathematica and my little package (OEIS Package)  it is easy to use precomputed data from A061799 and  A003418, but the main code is slow, so I thought to use PARI/GP...

I confess I have no experience with Mathematica, Maple, PARI, or anything similar.  I'm simply coding in a general purpose compiled programming language.   It's Go, actually, but I'm using no special features that aren't in C or Fortran or whatever.  I'm sure if I do much more of this I'll want to learn some of these numerical languages, if for nothing else just so I can read other programs!

Sonia

[Peter Luschny]

Hello Enrique,

> Well, failure is an option, at least we have done some job for the other
> sequences.

Absolutely. It was only a failure computationally.
And, as Matt said, it is the best way to understand A094348.

Clearly it is hard, what we are considering is the
distribution of the prime numbers, though this is not
obvious at first sight. I do believe that the
Vandermast numbers, as I call them -- Matt is somewhat
ambivalent about this -- are numbers with high significance.

> because I went, on saturday morning, to look for some catharellus
> lutescens and I return home just to make a nice tortilla (omelette).

Please send me such a tortilla (via Internet?)!

> *we don't  know up to which k we have to go*

> What if we calculate the sequence of k? (The least k)

I think we have to look at the prime factorization.
There is the clue to a fast algorithm.

Also look at the tau-column at
http://oeis.org/wiki/User:Peter_Luschny/A057641A094348
and observe the dramatic effect of applying the Lagarias
transformation: For n=141 tau=20160 is reduced to tau=64.
What is the explanation?

Cheers, Peter

[Enrique P?rez Herrero]

Hi, Peter:

I´ve just been reading Lagarias´s paper but I´ve notice that I did not understand anything, I´ll try to study it in deep.

http://arxiv.org/PS_cache/math/pdf/0008/0008177v2.pdf

Lagarias writes something about http://oeis.org/A004490, the Colossally abundant numbers, this numbers seem to have the following properties:

 

i)    A094348(n) divides A004490(n), this seems not to be very strange.

ii)   omega(A004490(n))=n, this looks like a very interesting property.  I would like to be able to prove it. (maybe it is already settled, but I´m completely out of this topic)

iii) I remark this comment from Lagarias´s article that looks that can be applied also to our A094348:

Superabundant and colossally abundant numbers were studied1 in detail by Alaoglu and Erd˝os [1]

in 1944. As evidenced in the table, colossally abundant numbers consist of a product of all the

small primes up to some bound, with exponents which are nonincreasing as the prime increases.

The values of these exponents have a characteristic smooth shape which can be almost completely

described

Cheers, Enrique.

[Reinhard Zumkeller]

A belated Thank You to Peter for having invited me to this group! We
will find a lot of mutual suggestions and open discussion, hopefully.

And also a late response to the first thread: "A good algorithm for
A094348"; at first I was just attracted by the strange sounding
definition in A094348; later I got fascinated and started a little
background job in my brain. And eventually I started programming ….

What I did:
I was following Peter's suggestion from 1st of december:
> At the moment I believe we need two things:
> (1) A fast way to generate A025487
> (2) a filter which reduces A025487 to A094348.

(1) was a nice challenge; my Haskell program produces b-files for
A025487 of length, e.g.
100000 (2.6 MB) in 22 sec
1000000 (35,6 MB) in 1 min
-- I don't think that my algorithm is novel ;-)

Examples:
A025487(100000) = 8371543500973965312000 = 2^18 * 3^16 * 5^3 * 7^3 * 11^3 * 13
A025487(999978) = 27303862554912628857041140471200 = 2^5 * 3^3 * 5^2
* 7^2 * 11^2 * 13^2 *17^2 * 19^2 * 23 * 29 * 31 * 37 * 41 * 43 * 47 *
53 * 59 * 61
A025487(1000000) = 27310691067617083392000000000000 = 2^34 * 3^18 * 5^12 * 7^5

(2) I didn't find the requested "good algorithm" to give files for
10000 or just 1000 terms of A094348, but I got at least some more
terms than in the current
http://oeis.org/wiki/User:Peter_Luschny/A057641A094348.

My largest and last term:
A094348(230) = 1318742342232339024000 = 2^7 * 3^3 * 5^3 * 7^2 * 11 *
13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 with 393216 divisors.

My filter is more or less based on brute force, not only concerning
time, but also space: it memorizes a l l current successful
j,k-pairs. I looked for but didn't find a way to avoid this.
So the search for a "good algorithm for A094348" will continue.

Best,
Reinhard

Attachments:
Vandermast.hs - program for A094348
PrimeSignatureMinima.hs - program for A025487
b094348--230rz.txt - {(n, A094348(n): 1 <= n <= 230}
(if desired, I could also deliver tau, omega, etc.)

2010/12/1 <ghod...@comcast.net>:
> On 1 Dez., 00:33, Psychedelic Geometry wrote:
>> This is an observation, maybe useless, about this sequence:
>> A000005(A094348(n+1))>=A000005(A094348(n)) this hold for the known
>> terms of the sequence:
>
> You're not alone in noticing this (see conjecture under
> http://oeis.org/A140999). 5354228880 is a counterexample, however (though
> perhaps not the smallest). As the smallest multiple of the first 23 positive
> integers, it belongs to A094348, but has only 1920 divisors, and a
> smaller member of A002182 has 2016.
>
> A002182(74) = 4655 851200 = 2 ^ 6 x 3 ^ 2 x 5 ^ 2 x 7 x 11 x 13 x 17 x 19
> Number of divisors:  2016
> A003418(23) = 5354 228880 = 2 ^ 4 x 3 ^ 2 x 5 x 7 x 11 x 13 x 17 x 19 x 23
> Number of divisors:  1920 (Source: http://www.alpertron.com.ar/ECM.HTM)
>
> All members of http://oeis.org/A002182 and http://oeis.org/A003418  belong
> to A094348.  A003418(23) is just the first member of A003418 to have fewer
> divisors than some smaller member of A002182. But I suspect that they all do
> except for a finite number of exceptions.  The intersection of A2182 and
> A3418 has definitely been proved finite; see
> http://oeis.org/A055492, http://oeis.org/A095921.
>
> http://oeis.org/A164377 shows the A094348 members that are not in A002182.
>
> Thanks for your interest, everybody, and good luck - I wish I could be more
> help.
>
> Best regards,
> Matt Vandermast
>
>

[Peter Luschny]

Hi Enrique

> I´ve just been reading Lagarias´s paper ...

Great! Next year I will open a thread on this.

> Lagarias writes something about [...] the Colossally
> abundant numbers

* abundant numbers = A002093, A002182, A005101, A006038, A004394;
* colossally abundant numbers = A004490,
* highly abundant numbers = A002093,
* superabundant numbers = A004394.

* highly composite numbers (A002182)
* least common multiples of 1 through n (A003418)
* deeply composite numbers (A095848)

What a zoo! I fact we need a classification with special
attention to David Wasserman's observations
72, 30240, 64864800 and 1470268800.

Something like this awesome classification of figurate numbers
given by Daniel Forgues [1]. Though I would prefer a kind of
inclusion diagram, or Hasse diagram to deal with these posets.
Good pages for the wiki I think!

> "The values of these exponents have a characteristic smooth
> shape which can be almost completely described"

... and this was also the observation which led finally to
Reinhard's breakthrough.

Cheers Peter

[1] http://oeis.org/wiki/Classifications_of_figurate_numbers

[Peter Luschny]

Hallo Reinhard,

nice to see you here, welcome!

> At the moment I believe we need two things:
> (1) A fast way to generate A025487
> (2) a filter which reduces A025487 to A094348.

> (1) was a nice challenge; my Haskell program produces [...]

> 1000000 (35,6 MB) in 1 min

Impressive.

> (2) I didn't find the requested "good algorithm" to give files for
> 10000 or just 1000 terms of A094348, but I got at least some more
> terms than in the current
> http://oeis.org/wiki/User:Peter_Luschny/A057641A094348.

... in the meantime I have included your results on this page.

> My filter is more or less based on brute force, not only concerning
> time, but also space: it memorizes a l l current successful
> j,k-pairs. I looked for but didn't find a way to avoid this.
> So the search for a "good algorithm for A094348" will continue.

OK, on the other hand I think we have now enough terms to make
some educated conjectures and check them numerically against
the tables.

After all we study this to crack the RH next year via Lagarias!
--

I wish a Happy Holiday Season to all of you!

Best, Peter

[Peter Luschny]

> Attachments: b094348--230rz.txt  - {(n, A094348(n): 1 <= n <= 230}

'Houston, we have a problem.'
Definition: A094348 Numbers n such that, for some numbers (j,k),
j<=k, n is the smallest positive multiple of j (or more) of
the first k positive integers.

k in {1,...,42} divides 1314361138437547200, but not k=43.
k in {1,...,42} divides 2628722276875094400, but not k=43.

[-188-] 1314361138437547200
[-194-] 2628722276875094400

'Uh, this is Houston. Uh, say again, please?'
Cheers, Peter

[Peter Luschny]

A new PARI script computes the first 50 terms in less than 30 seconds.
See A094348 (pending, see history).)

http://twitter.com/sequitter

[Peter Luschny]

> M. Hasler wrote..

>> MV: I think I can best explain the sequence by
>> MV: referring to sequence A096179: "Triangle read
>> MV: by rows: T(n,k) is the smallest positive integer
>> MV: having at least k of the first n positive integers
>> MV: as divisors."

> The problem for A094348 is that we don't know up to
> which k we have to go.

Let us call this the k-problem. It is a computational
problem; looking at it from the arithmetical side this
is an intriguing fact.

I submitted the following comment to A094348:

---
This sequence is also A096179 with duplicates deleted and
sorted. Let F(n) be the number of the row of A096179 which
has the first occurence of a(n) and M(n) = max{F(i),i <= n}.
Then the following table indicates this connection.

n |1,2,3,4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
20, 21
a(n)|
1,2,4,6,12,24,36,48,60,72,120,180,240,360,420,720,840,1260,1680,2520,5040
F(n)|1,2,4,3, 4, 8,18,16, 5, 9, 8, 18, 16, 9, 7, 16, 15, 21,
16, 9, 16
M(n)|1,2,4,4, 4, 8,18,18,18,18, 18, 18, 18, 18, 18, 18, 18, 21, 21,
21, 21
---

With regard to the k-problem it says that sometimes the 'k'
catches up with the 'n'; more precisely: The observation is
that the function M(n) has fixpoints. Apart from the
uninteresting cases 1,2,4 only one fixpoint shows up in
the table: n = 21.

Hhm, and in this case a(n) = 5040, the last n which breaks
the Robin criterion of the Riemann Hypothesis!

Maybe this is by pure chance. In any case it would be
interesting to find more fixpoints of H(n). However, this
seems beyond what we can do with our algorithms at hand.

Why is this so hard?

Peter

[Peter Luschny]

Typo: replace "fixpoints of H(n)" by "fixpoints of M(n)".

The k-problem now has an OEIS-name: A178938.
Ok, not yet, it is a draft.

So let us see how this child grows :)

Peter

[Enrique Pérez Herrero]

Hello, I´ve been using my spare time this few days of vacations in
reading about Riemann Hypothesis, I´ve broke my promise of avoiding
RH, because it is very very far from my scarce knowledge of maths, and
I´ll better dedicate myself to trivialities in NT to see if I can
learn something (like a primer on Analytic NT).

Here you can find some articles I´ve found on the internet:
http://oeis.org/wiki/User:Enrique_P%C3%A9rez_Herrero/Riemann

[1] J. C. Lagarias, An elementary problem equivalent to the Riemann
hypothesis, Amer. Math. Monthly, 109 (2002), 534-543
[2] Keith Briggs, Abundant Numbers and the Riemann Hypothesis,
Experimental Mathematics, Vol. 15 (2006), No. 2
[3] Keith Briggs, Notes on the Riemann hypothesis and abundant
numbers, 2005 April 21
[4] Alaoglu, L.; Erdős, P. (1944). "On highly composite and similar
numbers". Transactions of the American Mathematical Society 56 (3):
448–469. doi:10.2307/1990319. MR0011087. http://jstor.org/stable/1990319.
[5] Erdös, Pál, On highly composite numbers, J. London Math. Soc. 19,
130-133 (1944).
[6] YoungJu Choie; Nicolas Lichiardopol; Pieter Moree; Patrick Solé,
"On Robin’s criterion for the Riemann hypothesis", Journal de théorie
des nombres de Bordeaux, 19 no. 2 (2007), p. 357-372
[7] Patrick Solé, Michel Planat, "Robin inequality for 7-free
integers", arXiv:1012.0671v1, Dec, 3, 2010.

(If you know more... please tell it to me)

I´ve seen that both reformulations of RH, Robin´s and Lagarias´s deal
with an asymptotic bound of divisors sigma function, at the moment
like in [7] or [6] mathematicians have been able to prove this bound
for some subsets of integers, the special integers that can put in
serious dificulties RH are integers with many divisors in proportion,
like the Hardy-Ramanujan Integers described in [6] (page 367),
integers with e1>=e2>=...>=eS>=0 (where ei are the prime coef. in the
factorization), there are also many subsets of H-Ramanujan numbers
that can jeopardize the truth of RH, like colossally abundant (CA),or
superabundant (SA)...
And here is the question... Why does A094348 matters to RH?, because
this sequence contains many CA and SA numbers?

By the way I want to find CA and SA numbers in A094348, I´ve got some
code in Mathematica that can upload data from bfiles and search in
A094348 easily, but I would like to have more terms of A094348 before.

Peter, does your code can find 1000 terms of A094348?

Other question do you know where are Hardy-Ramanujan Integers in OEIS?
(I´m lazy and I don´t want to code them to find out)

More... Can we prove that A094348 is a subset of Hardy-Ramanujan
Integers?

Other idea is to look for some function f(p,n)=floor(g(p,n)) been g
monotonically decreasing that can give the exponents of the
factorization of this SA or A094348 numbers, for CA there are already
one (or at least an algorithm with a formula).

Best wishes for new year!

[Peter Luschny]

> Peter, does your code can find 1000 terms of A094348?

Well, depends. How long is your holiday? :)

If you mean by 'code' the snippet on OEIS the answer is no.
It is fine in the range indicated, and it is of educational
value, I hope. It is based on ideas I learned from David
Wasserman. The code clearly shows the two bottlenecks: Too
many numbers have to be scanned and the divisors-function.

However Reinhard already exercised the next step reducing
the number of test values. Compute first A025487. This
can be done fast.

[1]
[2]
[4]
[6, 8]
[12, 16]
[24, 30, 32]
[36, 48, 60, 64]
[72, 96, 120, 128]
[144, 180, 192, 210, 216, 240, 256]
[288, 360, 384, 420, 432, 480, 512]
[576, 720, 768, 840, 864, 900, 960, 1024]

In fact, leaving 1,2,4 aside, it is sufficient to look at
the sub sequence which is divisible by 3

[6]
[12]
[24, 30]
[36, 48, 60]
[72, 96, 120]
[144, 180, 192, 210, 216, 240]
[288, 360, 384, 420, 432, 480]
[576, 720, 768, 840, 864, 900, 960]

So we only have to check 29 values below 1024. Now you
can apply the code snippet to this (precomputed) sequence
just as it is applied in the OEIS version to n=12*k.

This brings the (to me) acceptable range somewhere to n<=250
(Reinhard computed 230). Hey, wait a moment, a month ago I
computed only the range n<=25. So there is hope that we
can reach our goal next year. :)

Thank you for the fine information on the RH you have
compiled. I will answer soon to your other questions.

> Best wishes for new year!

Happy New Year! Well, it's a prime year, so it has to
be a good year.

Cheers, Peter

P.S. Please can someone comment on my observation
[-188-] 1314361138437547200
[-194-] 2628722276875094400
Or do I overlook something? Thanks!

[Zumi]

Sorry for not having answered earlier …
But I do not really understand the problem.
Could it be, that you tried to refer a property that is n o t the
defining property of A094348?

Maybe it could help (at least to me), if you would look for examples
with smaller numbers,
e.g.:
k in {1,2,3,4,5,6,7,8,9,10,11,12} divides 27720, but not k=13
k in {1,2,3,4,5,6,7,8,9,10,11,12} divides 55440, but not k=13
k in {1,2,3,4,5,6,7,8,9,10,11,12} divides 83160, but not k=13
A094348(27) = 27720
A094348(31) = 55440
A094348(32) = 83160

But to fit the definition, we must probably check much more (j,k)
pairs to be checked !! …..
27720 ->
[1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,20,21,22,24,28,30,33,35,36,40,42,44,45,55,56,60,63,66,70,72,77,84,88,90,99,105,110,120,126,132,140,...
55440 ->
[1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,22,24,28,30,33,35,36,40,42,44,45,48,55,56,60,63,66,70,72,77,80,84,88,90,99,105,110,112,120,...
83160 ->
[1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,20,21,22,24,27,28,30,33,35,36,40,42,44,45,54,55,56,60,63,66,70,72,77,84,88,90,99,105,108,110,120,...

Anyway: next year we will progress! ;-)
Best regards + happy New Year
Reinhard

[Peter Luschny]

Hello Reinhard!

> But I do not really understand the problem.
> Could it be, that you tried to refer a property that
> is n o t the defining property of A094348?

Yes. I see it now. My own thoughts interfered here.

(I am trying to find a variant which has similar features
with respect to the Lagarias sequence (i.e. which is a lower
bound > 0 of A057641) but which is easier to compute.)

Thank you for the clarification!

Cheers, Peter

[Peter Luschny]

> Reinhard Zumkeller wrote:
> b094348--230rz.txt - {(n, A094348(n): 1 <= n <= 230}

I computed all A094348(n) < 2^77 and can confirm your values.

A nice plot via http://twitter.com/sequitter

Peter

[Peter Luschny]

Reinhard wrote:

> Anyway: next year we will progress! ;-)

Sure! Next year is now :)

Here my first, very early and very rough estimate
of A094348(1000). It is in the neighborhood of

74224306218661920611968383996168554711900917077570550213879203517460111716080

Such an estimate can help to choose the right tools for the
final attack: <<< The SEQCOMP 1000-th Term Challenge >>>

In the spirit of:
http://www-m3.ma.tum.de/m3old/bornemann/challengebook/index.html

Cheers, Peter

[Peter Luschny]

Enrique Pérez Herrero wrote:
> And here is the question... Why does A094348 matters to RH?

Well, first of all note that this is all experimental and
exploratory, I do not make any claims. My personal approach to
A094348 comes via Lagarias. It is sketched in A181852.
http://oeis.org/A181852 There you find the sentence:

"Further the inequality 0 <= A057641(lcm{1,2,3,4,5}) is in
agreement with (Lagarias' formulation of) the Riemann hypothesis."

Now, as it is clear, A094348 is a generalization of lcm{1,2,...,n},
a straightforward and good one, well now ...

And already Пафну́тий Льво́вич Чебышёв attacked the prime
number theorem via lcm{1,2,...,n}, though this function is
nowadays better known under Pafnuty Lvovich's last name.

So basically my question is: Does A057641(A094348) outline
a lower bound of the Lagarias function as sketched on my
OEIS-user page RiemannLagarias.

Want more wild speculations? Here we go: Look at the plot
https://sites.google.com/site/seqcomp/seqsupp/plot094348
I assume that A094348 will crawl up this straight line
with only small oscillations. If all this is true it might
be easy to conjecture a simple lower bound > 0 for A057641
which puts aside the high mountain of noise which is in
A057641 (again, look at the plot on RiemannLagarias page).

To find out more about this it is important to contribute
to the <<< The SEQCOMP 1000-th Term Challenge >>> :)

Cheers, Peter

[Matthew Vandermast]

> Best wishes for new year!

I also wish everyone reading a happy new year, and thank everyone who
has investigated and extended A094348 and A096179. (Also, thanks to
Peter for the recent help with posting here.)

Best to all,
Matt Vandermast

[Zumi]

Dear Peter,

this is good news,
thanks for this check and the confirmation!
This is also an encouragement to go ahead ;-)

Best,
Reinhard

[George Beck]

Another example of double enumeration: count the partitions
of n into k parts with smallest part i and with largest part
j. That gives a matrix M(n). The row sums are A008284 and
the column sums are A026794. Too many zeros for the
determinant not to be zero, so add the identity matrix I.
Then det(I + x M(n)) = (x+1)^d(n), where d(n) is the number
of divisors of n. I just found that last night! No proof. It
is hard to see this as being trivial. I don't know if it is
important, but it is surprising to me. Maybe it is connected
to Euler's
http://mathworld.wolfram.com/PartitionFunctionP.html (13).

IntegerPartitionsSquare[n_] :=
Module[{in, max, min, trmaxmin, vpos, m},
in = IntegerPartitions[n];
max = Max /@ in;
min = Min /@ in;
trmaxmin = Transpose@{max, min};
vpos = {Length@#, First@#} & /@ Split@Sort@trmaxmin;
m = Table[0, {i, n}, {j, n}];
Map[(m[[#[[2, 1]], #[[2, 2]]]] = #[[1]]) &, vpos];
m]

[Peter Luschny]

Zumi wrote:

> This is also an encouragement to go ahead ;-)

Yes. And sequitter just told me:

A094348 A new Pari script computes the first 100 members
in less than 6 seconds. Visit the seqcomp site where you
can find the script!

[Peter Luschny]

I did not change the name of the discussion.

There might be a bug in groups.google.
Maybe there are to many messages in the
A094348 thread for Google (my last message
was number 51 as far as I can see).

Peter

[Enrique P?rez Herrero]

Hello, this is my opinion about your proposal for A094348:

prime omega ("small omega") number of distinct primes too high, the last terms you computed (259) have more trailing zeros digits.  

Bye.

[Peter Luschny]

Hello Enrique, this is a very nice answer!

So now we *have* to compute A094348(1000)
to see what the truth is :)

Cheers, Peter

[Enrique P?rez Herrero]

I think that the first milestone to know something about A094348 is  to find an algorithm for:

We have a set of n integers A, and then we have to choose k elements in order to minimize the LCM of  this k elements.

Or in an intermediate step:  We have k elements and we can replace just one of them for another one, which element we must replace (if any) if we want to minimize the LCM of the new set?.

This problem is a kind of optimization problem in trees, where the tree is a tree of divisibility, and divisibility is a partial order in A.

I apologize for my english (and math) but I hope to be understood.

Bye.

 

[Peter Luschny]

Howdy!

(1) Enrique, did you notice that your data fit NonlinearModelFit
[dataprimeomega, a*x^(1/2), {a}, x]] gives 1.65940146 Sqrt[x]
and that this constant is cos(Pi*6/23) + sin(Pi*22/51)?

(2) I also looked at the tau of A094348 (DivisorSigma[1,..]
in Mathematica). Surprise or not? Any comments?
https://sites.google.com/site/seqcomp/seqplots/a094348tau

EPH> to find an algorithm for: We have a set of n integers A,
EPH> and then we have to choose k elements in order to minimize
EPH> the LCM of this k elements.

(3) Do you have any indication that this way can beat the way
via integer partitions which I uploaded yesterday? It computes
A094348(n), n<=100 in less than five seconds. I am quite
pleased with this result and will not look in another direction
before I have been shown an alternative which can beat this.
https://sites.google.com/site/seqcomp/seqlistings/a094348pari

Cheers, Peter

[Peter Luschny]

¡Buenas tardes!

I found another two sequences informative in
the study of A094348.

A182941 Sum of divisors of A094348. The first nine
terms are the same as in A007626 and A063072.

A182940 Read A094348 term-by-term, compute the
divisors of each term, write down any divisors
not seen before.

1 [1]
2 [2]
4 [4]
6 [3, 6]
12 [12]
24 [8, 24]
36 [9, 18, 36]
48 [16, 48]
60 [5, 10, 15, 20, 30, 60]
72 [72]

And here the homework for the investigative
seqcomputer: If you apply the technique of
A182940 not to the 'ordinary' divisors but
to the 'prime' divisors, what do you get?
(Note that order matters!)

Cheers, Peter

[Peter Luschny]

> Reinhard wrote:
> Vandermast.hs - program for A094348
> PrimeSignatureMinima.hs - program for A025487
> b094348--230rz.txt - {(n, A094348(n): 1 <= n <= 230}

Though I was avid for learning Reinhard's ideas from his programs
my ignorance of Haskell detained me. So I asked Reinhard
for some explanations. Reinhard came up with an exposition
of his program which is too nice to be buried in my mailbox.

So here is Reinhard's exposition now:
https://sites.google.com/site/seqcomp/seqlistings/a094348haskell

Thank you Reinhard!

Peter

[Peter Luschny]

> On 3 Jan., 22:16, Enrique wrote:

> We have a set of n integers A, and then we have to choose k elements in
> order to minimize the LCM of  this k elements.
> Or in an intermediate step:  We have k elements and we can replace just one
> of them for another one, which element we must replace (if any) if we want
> to minimize the LCM of the new set?.

See the also the new paper: arXiv:1101.0142v1. A nice paper with good
references to our problem, fairly advanced though and not algorithmic
oriented.

You might also want to google for
M. Nair, On Chebyshev-type inequalities for primes, Amer. Math.
Monthly 89 (1982)

And while I am at link collecting, we should not forget Flammenkamp's
efforts
http://wwwhomes.uni-bielefeld.de/achim/highly.html
After all A002182 is just a sub-sequence of the Vandermast numbers.

I think Ramanujan's numbers are only a crude approximation to
the idea of the finespun Vandermast numbers.

Cheers, Peter

[Enrique P?rez Herrero]

Thank you, Peter:

 

I will read them as soon as I have a little bit of time, I have so much homework to do...

At the moment I´m having a lot of traveling by work and I could not sacrifice myself to the godess of math as I would like to.

I think that we may try to prove some properties of the sequences, this is paper and pen, instead of computer, like:

Are the A094348 numbers a subset of H-Ramanujan numbers? this can prove a very nice property of the prime exponents of A094348, very crude but this is the first step.

-------------------

This week in my little spare time I been doing the following:

1) if you use a recursive formula with memorization you can calculate the first 2000 terms of A00341 in 0.031 seconds  instead of 3.515

A003418[1] := 1;

A003418[n_] := A003418[n] = Block[{$RecursionLimit = 2000}, LCM[n, A003418[n - 1]]];

 

2) The numbers A003418 appear in A094348 at the positions: 

{1, 2, 4, 5, 9, 9, 15, 17, 20, 20, 27, 27, 38, 38, 38, 42, 53, 53, 68, 68, 68, 68, 86, 86, 92, 92, 100, 100, 118, 118, 136, 140, 140, 140, 140, 140, 157, 157, 157, 157, 179, 179, 203, 203, 203, 203, 225, 225, 235, 235, 235, 235}

This is a try to predict terms in the neighbourhood of  A094348(1000), we know the figures, but we don´t know where they will be.

3) A061799(p)=A061799(p+1) if p>3 is a prime.

4) I want to create a new sequence like http://oeis.org/A096179 but with maximum instead of minimum.

Guten nacht, y hasta mañana si Dios quiere.

[Peter Luschny]

Hi Enrique!

Many nice ideas. I hope I can check some of them tomorrow.

> Are the A094348 numbers a subset of H-Ramanujan numbers?

If you mean A002182, yes. I do not know if the are 'officially'
called 'Ramanujan numbers'; however, see the link to Ramanujan's
paper at A002182.

> This is a try to predict terms in the neighbourhood of
A094348(1000)

Flammenkamp computes A002182 up to 1199. Our A094348(1000)
lies somewhere around A002182(1060) (late night guess),
which is around 2.0e+080.

A good question for your Mathematica notebook is:
How dense does A002182 lie in A094348? Then you might
get a good estimate of A094348(1000) by extrapolation.

> I want to create a new sequence like http://oeis.org/A096179
> but with maximum instead of minimum.

Very good idea!

Cheers, Peter

[Enrique Pérez Herrero]

The new sequence promised is:

A179661: Triangle read by rows: T(n,k) is the largest least common
multiple of any k-element subset of the first n positive integers.

Best Regards, Enrique.

[Peter Luschny]

Hi Enrique!

Very nice. The next step is to convert it to a linearized
sequence, that is, to look for a counterpart analogous to what
Matthew's A094348 is to his A096179.

Matt's recipe (throw all terms in one pot and sort) will not
work here. The first column acts like a spoiler sequence which
will give us in the long run all positive integers trivializing
everything. So let us exclude this column. Cutting a row as
soon as it becomes stationary things then look like:

[index], [A179661_row]
[2], [2]
[3], [6]
[4], [12]
[5], [20, 60]
[6], [30, 60]
[7], [42, 210, 420]
[8], [56, 280, 840]
[9], [72, 504, 2520]
[10], [90, 630, 2520]
[11], [110, 990, 6930, 27720]
[12], [132, 990, 6930, 27720]
[13], [156, 1716, 12870, 90090, 360360]
[14], [182, 2002, 18018, 90090, 360360]
[15], [210, 2730, 30030, 120120, 360360]
[16], [240, 3120, 34320, 240240, 720720]
[17], [272, 4080, 53040, 583440, 4084080, 12252240]
[18], [306, 4080, 53040, 583440, 4084080, 12252240]
[19], [342, 5814, 77520, 1007760, 11085360, 77597520, 232792560]
[20], [380, 6460, 83980, 1007760, 11085360, 77597520, 232792560]
[21], [420, 7980, 135660, 1763580, 19399380, 77597520, 232792560]
[22], [462, 8778, 149226, 1939938, 19399380, 77597520, 232792560]

Remembering Maximilian's k-problem we cautiously distill the
associated sequence as

EPH = [2, 6, 12, 20, 30, 42, 56, 60, 72, 90, 110, 132,
156, 182, 210, 240, 272, 280, 306, 342, 380, 420, 462]

Let's try to find a name for this sequence. "EPH(n) is the
largest least common multiple for at least one subset of the
first n positive integers with more than one element."
Is this correct?

We might hope that we can apply the sequence pair [A094348,EPH]
to some more complex situations where the basic min/max idea
carries over to some lower and upper bounds of ..?
Hhm, so much more work remains to be done ...

The program is in the appendix.

Cheers, Peter

A179661_row := proc(n)
local k, L, l, R, LASTL, comb;
if n = 1 then R:= 1 else R := NULL fi;
L := NULL;
for k from 2 to n do
comb := iterstructs(Combination(n), size=k):
while not finished(comb) do
l := nextstruct(comb);
L := max(L, ilcm(op(l)));
od;
if LASTL <> L then R := R,L; fi;
LASTL := L; L := NULL;
od;
{R} end:

EPH := proc(m)
local S,i,T; S:= {};
for i from 1 to m do
T := A179661_row(i);
S := S union T;
print([i],sort(convert(T,list)));
od;
sort(convert(S,list)) end:
EPH(22);

[George Beck]

That remark about d(n) was very silly (it's completely obvious)--sorry!

- George