LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 04-09-2021, 01:01 PM   #16
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled

Let's try sequences of squares
Code:
4 4 
1 3 1 - circle is closed
.......
4 9 ..
1 3 6 ...
......
4 16 ...
1 3 13 ... 
...
extend by next square as long as there is no repetition.

Last edited by igadoter; 04-09-2021 at 01:36 PM.
 
Old 04-09-2021, 01:22 PM   #17
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655
Sorry to delay posting the code - it was after 3AM when finished and needed a little cleanup - here it is (and apologies if I broke anything during housekeeping!)

circle.txt

I have commented the header file with more complete details of the basis of my strategy, and the source code with hints where the implementation may be obscure, hope it is readable.

What I refer to as "bottom-up" pairings has a few subtleties but I have explored it in some detail and reduced the logic to only what is necessary, and am confident it is sound. If anyone thinks otherwise I would appreciate an example of an actual exception within the range of values under test.

Indeed, I am confident this may be taken as proof that there is a single solution and its mirror.

In addition, it suggests answers to a few earlier questions:

Code:
* Can there be such circles of more than 32 integers?
    Maybe not (but see Gazl's post #20 below!) - An unavoidable gap is produced by 33, and higher numbers (also evident in shape of listing in header)
* Can you remove any single number and have the circle remain valid?
    Probably not - the sequence is fully deterministic and it is difficult to see how to remove anything and close the circle
It will accept arguments for list starting point and listing direction, for example:

Code:
./circle 17 rev
17  (49, 36)
32  (36, 49)
4   (25, 36)
21  (49, 25)
28  (36, 49)
8   (9, 36)
1   (16, 9)
15  (25, 16)
10  (36, 25)
26  (49, 36)
23  (25, 49)
2   (16, 25)
14  (36, 16)
22  (49, 36)
27  (36, 49)
9   (25, 36)
16  (36, 25)
20  (49, 36)
29  (36, 49)
7   (25, 36)
18  (49, 25)
31  (36, 49)
5   (16, 36)
11  (36, 16)
25  (49, 36)
24  (36, 49)
12  (25, 36)
13  (16, 25)
3   (9, 16)
6   (36, 9)
30  (49, 36)
19  (36, 49)

Last edited by astrogeek; 04-09-2021 at 07:05 PM. Reason: tpoys, shameless face saving!
 
1 members found this post helpful.
Old 04-09-2021, 02:03 PM   #18
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Thanks, astrogeek. Will study your code.
Quote:
Originally Posted by astrogeek View Post
* Can you remove any single number and have the circle remain valid?
Probably not - the sequence is fully deterministic and it is difficult to see how to remove anything and close the circle
I have (accidentally?) produced some valid circles of squares with some digits missing, e.g
Code:
 
25 24 12 13 23 26 10 15 21 28 8 17 32 4 5 31 18 7 29 20 16 9 27 22 14 11
and at least one 32 element linear array that doesn't wrap around to form a ring (first and last elements don't sum to a square):
Code:
 
1 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15 21 28 8 17 32 4 12 13 3 6 30 19
Of course, neither of these meet the challenge of a valid 32 element ring, and both involve completely different sequences, not the removal of digits from a (the?) valid ring

I think there were one or more valid rings of 31 digits. The missing digit was 2, if i remember correctly. If i can reproduce it, will post it here.

Last edited by dogpatch; 04-09-2021 at 02:15 PM. Reason: add thanks and caveat
 
1 members found this post helpful.
Old 04-09-2021, 02:22 PM   #19
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655
Quote:
Originally Posted by dogpatch View Post
I have (accidentally?) produced some valid circles of squares with some digits missing, e.g
Code:
 
25 24 12 13 23 26 10 15 21 28 8 17 32 4 5 31 18 7 29 20 16 9 27 22 14 11
Indeed! I had typed a third question to the effect...

Code:
* Can there be other valid circles of fewer numbers?
    Almost certainly. While it is difficult to see a way to remove any single number and rejoin the ends,
    it is easy to see smaller rings, or removal of larger segments and be able to rejoin the ends.
But I had not fully explored it and decided it was too vague... but here now for what it is worth!

One inportant aspect of "with a few numbers missing" is whether they are missing from the end, leaving the list complete in some sense, or missing from within leaving gaps. Sets of numbers with internal discontinuities seem much easier to join into rings ad hoc whereas a continuous list imposes a more difficult constraint I think.

Quote:
Originally Posted by dogpatch View Post
and at least one 32 element linear array that doesn't wrap around to form a ring (first and last elements don't sum to a square):
Code:
 
1 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15 21 28 8 17 32 4 12 13 3 6 30 19
That one doesn't count!

Quote:
Originally Posted by dogpatch View Post
I think there were one or more valid rings of 31 digits. The missing digit was 2, if i remember correctly. If i can reproduce it, will post it here.
I'd be interested to see that one!
 
1 members found this post helpful.
Old 04-09-2021, 02:24 PM   #20
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
Here's the amazing_circle sequence for 1-50:
Code:
1, 3, 6, 10, 15, 49, 32, 4, 5, 11, 14, 50, 31, 18, 46, 35, 29, 7, 9, 27, 22, 42, 39, 25, 24, 40, 41, 8, 17, 47, 2, 34, 30, 19, 45, 36, 28, 21, 43, 38, 26, 23, 13, 12, 37, 44, 20, 16, 33, 48.
This one took over 6 mins cpu time to calculate using my sequence finding routine. I've found many other lengths generate a valid sequence, though not all (1-31 being one of the ones that fails to solve).

Last edited by GazL; 04-09-2021 at 02:29 PM.
 
2 members found this post helpful.
Old 04-09-2021, 02:40 PM   #21
astrogeek
Moderator
 
Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1}
Posts: 5,616
Blog Entries: 11

Rep: Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655Reputation: 3655
Quote:
Originally Posted by GazL View Post
Here's the amazing_circle sequence for 1-50:
Code:
1, 3, 6, 10, 15, 49, 32, 4, 5, 11, 14, 50, 31, 18, 46, 35, 29, 7, 9, 27, 22, 42, 39, 25, 24, 40, 41, 8, 17, 47, 2, 34, 30, 19, 45, 36, 28, 21, 43, 38, 26, 23, 13, 12, 37, 44, 20, 16, 33, 48.
This one took over 6 mins cpu time to calculate using my sequence finding routine. I've found many other lengths generate a valid sequence, though not all (1-31 being one of the ones that fails to solve).
So some longer sequences are possible, very interesting!

I have been so preoccupied with my own code in limited free time and have not had a chance to look into yours, but will do so over weekend. Thanks!
 
2 members found this post helpful.
Old 04-09-2021, 05:43 PM   #22
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
Here's a 31 element ring of squares:
Code:
30 19 17 32 4 5 31 18 7 29 20 16 9 27 22 14 11 25 24 12 13 23 26 10 15 21 28 8 1 3 6
but neither this nor the 26 element ring in post #18 above meet the challenge, because, although they wrap around as a ring of data, they still include values 1 thru 32, beyond their proper range. The 31 element ring is missing a 2, not a 32. And astrogeek is right, of course; the missing digits are outside the ring. The 2 could not be validly inserted in any location without completely re-arranging the sequence, and so could not be described as being removed from inside a valid 32 element ring.
 
1 members found this post helpful.
Old 04-09-2021, 06:20 PM   #23
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
Here's an updated version of my program. It now takes number of elements and start value as arg1 and arg2 respectively to aid experimentation.

It runs much faster when compiled -O3, and this version has replaced the O(n) value_used() function in the original with an O(1) lookup which also helped speed it up significantly.

Running ./amazing_circle 51 takes about two minutes here.
Running ./amazing_circle 52 takes over six minutes, and calculation time starts to get significant as the sequence size gets larger.

Last edited by GazL; 04-15-2021 at 07:05 AM.
 
1 members found this post helpful.
Old 04-10-2021, 05:50 AM   #24
GazL
LQ Veteran
 
Registered: May 2008
Posts: 5,923

Rep: Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899Reputation: 3899
And a final version.

Purely performance improvements this time: generating an index of the pairs by value rather than doing a sequential search in find_next() brings the 1-52 calculation time down from 6 minutes to 33 seconds.

Last edited by GazL; 04-15-2021 at 07:05 AM.
 
Old 04-10-2021, 07:19 AM   #25
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled
Thanks, this
Code:
% time for i in `seq 52` ; do echo -n "$i  "; ./a.out $i >/dev/null && echo 1  || echo 0 ; done
says starting from 32 there is always such sequence, here is my timing
Code:
 
real	2m2.535s
user	2m2.336s
sys	0m0.056s
on
Code:
% lscpu | grep name
Model name:          Intel(R) Core(TM) i5-3320M CPU @ 2.60GHz
essentially I see drop of performance at 52, say the same as above but up to 51, gives
Code:
real	0m54.465s
user	0m54.285s
sys	0m0.046s
so to calculate ./a.out 52 took almost the same time as to calculate all earlier sequences. At the end I can assure that if there is only one sequence starting with 1 then there are no other sequences.
 
Old 04-10-2021, 07:33 AM   #26
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled
Where beauty lies?

Genetic modification. Let see hot looks like sequences for 32 and 33
Code:
 
1  8  28  21  4  32  17  19  30  6  3  13  12  24  25  11  5  31  18  7  29  20  16  9  27  22  14  2  23  26  10  15
1  8  28  21  4  32  17  19  30  6  3  13  12  24  25  11  5  20  29  7  18  31  33  16  9  27  22  14  2  23  26  10  15
as you see these sequences share very large common prefix start from 1 up to 5, notice
Code:
31  18  7  29  20
20  29  7  18  31
they are reverse of each other -now 33 in new insertion and the rest is the same as in the first sequence. Why we slice the first sequence at 31 and 16? It's evident 31+33= 64 is a square, 16+33=49 is a square! So it seems it is possible to create new sequence from existing one through slicing, reversing and insertion. It is pure bio-technology . I really deserve for this good beer. Nope, doctor's say can't drink, think chocolate be enough sigh.
 
2 members found this post helpful.
Old 04-10-2021, 08:55 AM   #27
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 488

Original Poster
Blog Entries: 4

Rep: Reputation: 237Reputation: 237Reputation: 237
As expected, you fellows are leaving me in the dust, even though i had a head start.

Quote:
Originally Posted by igadoter View Post
Genetic modification. Let see hot looks like sequences for 32 and 33
Code:
 
1  8  28  21  4  32  17  19  30  6  3  13  12  24  25  11  5  31  18  7  29  20  16  9  27  22  14  2  23  26  10  15
1  8  28  21  4  32  17  19  30  6  3  13  12  24  25  11  5  20  29  7  18  31  33  16  9  27  22  14  2  23  26  10  15
as you see these sequences share very large common prefix start from 1 up to 5, notice
Code:
31  18  7  29  20
20  29  7  18  31
they are reverse of each other -now 33 in new insertion and the rest is the same as in the first sequence. Why we slice the first sequence at 31 and 16? It's evident 31+33= 64 is a square, 16+33=49 is a square! So it seems it is possible to create new sequence from existing one through slicing, reversing and insertion. It is pure bio-technology . I really deserve for this good beer. Nope, doctor's say can't drink, think chocolate be enough sigh.
This sounds exactly like what astrogeek has been saying about deterministic sequences, series that must exist, or their mirrors. His logic makes it possible to identify such sequences before starting any recursive looping. Such sequences then remain valid and deterministic in ever larger rings. Not only that, but new deterministic sequences may then be identified as longer rings are developed.

I predict that combining this with Gazl's enhanced performance could greatly reduce run time and make larger rings and, possibly, reveal multiple valid rings for some ring sizes.

Last edited by dogpatch; 04-10-2021 at 09:04 AM.
 
1 members found this post helpful.
Old 04-11-2021, 02:25 PM   #28
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled
In this place story started https://m.facebook.com/story.php?sto...cus_composer=0 I really hope we will finish this. My idea of "genetic" modifications is good starting point to create more efficient program.
 
Old 04-12-2021, 02:17 AM   #29
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,490

Rep: Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532Reputation: 5532
I tried to improve [speed up] that amazing_circle_v2.1.c, but was not that easy.
Actually [for 51] the find_next function was called 507 343 990 times.
 
Old 04-12-2021, 04:10 AM   #30
igadoter
Senior Member
 
Registered: Sep 2006
Location: wroclaw, poland
Distribution: many, primary Slackware
Posts: 2,248
Blog Entries: 1

Rep: Reputation: Disabled
Ok let me explain what I'm thinking of in more details. The program (or procedure) takes as input amazing circle and extends it by one. As input let take circle of 32 number (1.. 32). Now
Code:
33+3=36
33+16=49
33+31=64
now we need to find numbers 3, 16, 31 in input circle. Each pair (3,16), (3,31), (16,31) divides circle into two "arcs" [3,16] - the first one reaches 16 going forward - second backward.
This [3,16) means the arc without 16, (3,16] - arc without 3. Let reverse [3,16). then 3 and 16 will be adjacent and I can insert 33 between them. But reverse may not give new amazing circle. Condition must be satisfied. Ok some picture
Code:
1  8  28  21  4  32  17  19  30  6  3  13  12  24  25  11  5  31  18  7  29  20  16  9  27  22  14  2  23  26  10  15
this is circle of 32 numbers let's look for pair 3,16 one of arcs [3, 16] is
Code:
3  13  12  24  25  11  5  31  18  7  29  20  16
and [3,16) is
Code:
3  13  12  24  25  11  5  31  18  7  29  20
reverse is
Code:
20 29 7 18 31 5 11 25 24 12 13 3
this reversing is operation did on circle so output is
Code:
1  8  28  21  4  32  17  19  30  6  20  29  7  18  31  5  11  25  24  12  13  3  16  9  27  22  14  2  23  26  10  15
now 3 and 16 are adjacent and I can put between them 33. But construction fails: there are two consecutive numbers 6 20 which do not sum up to square 6+20=26. Verifying all pairs and all arcs finally we succed with 31 and 16.
 
  


Reply

Tags
circle, perfect square, programming challenge, ring, ring data type


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
damnit!!! i cant see what im typing.. fonts are squares iLLuSionZ Linux - Newbie 22 11-18-2003 03:36 PM
characters as squares in mozilla icyfire Linux - Software 4 09-18-2003 04:22 PM
white squares appear on screen saver? bongo.hickup Linux - Hardware 0 06-13-2003 03:51 AM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 12:41 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration