[seqfan] Re: Worry about old sequence, A030077, paths in K_n

[David Applegate]

I worry about using floating point (extended or not) to check if 
different sums of square roots are equal or not.  Using finite precision 
for this is extremely tricky This is a notoriously hard problem in 
general.  For example, to see that
sqrt(7)+sqrt(14)+sqrt(39)+sqrt(70)+sqrt(72)+sqrt(76)+sqrt(85) != 
sqrt(13)+sqrt(16)+sqrt(55)+sqrt(67)+sqrt(73)+sqrt(79) you already need 
more than double-precision floating point (their difference is 10^-19, 
see 
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3838&rep=rep1&type=pdf).
There is a randomized polynomial time algorithm for testing equality, 
but it isn't just compute the result to enough precision.

Some links with additional information:
https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010
https://topp.openproblem.net/p33
https://refubium.fu-berlin.de/bitstream/handle/fub188/18449/1993-13.pdf;jsessionid=89F489131478714C98250CFA34AFBFE7?sequence=1

-Dave

On 4/2/2022 5:05 AM, Sean A. Irvine wrote:
> So far I can verify to A030077(14):
>
> 2022-04-02 21:46:54 1
> 2022-04-02 21:46:54 1
> 2022-04-02 21:46:54 1
> 2022-04-02 21:46:54 3
> 2022-04-02 21:46:54 5
> 2022-04-02 21:46:54 17
> 2022-04-02 21:46:54 28
> 2022-04-02 21:46:54 105
> 2022-04-02 21:46:54 161
> 2022-04-02 21:46:54 670
> 2022-04-02 21:46:55 1001
> 2022-04-02 21:47:00 2869
> 2022-04-02 21:47:58 6188
> 2022-04-02 22:01:58 26565
>
> I adapted my existing program for A007874 to this case.  I'm not sure why I
> skipped over it before, but perhaps the dihedral group confused me.  The
> program uses 50 digits of precision for the length determination. I feel
> like it should be possible to do this without any kind of precision limit,
> but I don't have the time for that now.  I'll leave it running overnight.
>
> I'll also start a run for A007874 itself which also has four additional
> terms with a(15) looking a little suspicious.
>
> Sean.
>
>
>
> On Sat, 2 Apr 2022 at 16:22, Neil Sloane <njasloane at gmail.com> wrote:
>
>> To Seq Fans, The creator of an interesting sequence,  A030077, Daniel
>> Gittelson, submitted 12 terms in 1999, and 4 more terms were added in 2007
>> by a former editor. Daniel G. wrote to me today, expressing doubt about the
>> 4 additional terms.
>>
>> He says he interrupted his study of sequences to pursue a medical career,
>> but now that he is retired, he can return to combinatorics.
>>
>> It would be nice if someone could verify the terms! (It is not at all
>> obvious to me how to do this.)
>>
>> Neil Sloane
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
> --
> Seqfan Mailing list - http://list.seqfan.eu/