12
\$\begingroup\$

Introduction

Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers.

The first challenge in this series is to output a(n) for a given n as input, where a(n) is A064413, also known as the EKG sequence because the graph of its values resembles an electrocardiogram (hence the "How does this feel" reference). Interesting properties of this sequence are that all positive integers appear exactly once. Another notable feature is that all primes occur in increasing order.

Graph of the first 80 values of the EKG sequence

Task

Given an integer input n, output a(n).

\$a(n)\$ is defined as:

  • \$a(1) = 1; a(2) = 2;\$
  • for \$n > 2\$, \$a(n)\$ is the smallest number not already used which shares a factor with \$a(n-1)\$

Note: 1-based indexing is assumed here; you may use 0-based indexing, so \$a(0) = 1; a(1) = 2\$, etc. Please mention this in your answer if you choose to use this.

Test cases

Input | Output -------------- 1 | 1 5 | 3 20 | 11 50 | 49 123 | 132 1234 | 1296 3000 | 3122 9999 | 10374

Rules

  • Input and output are integers (your program should at least support input and output in the range of 1 up to 32767)
  • Invalid input (floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
  • Default I/O rules apply.
  • Default loopholes are forbidden.
  • This is , so the shortest answers in bytes wins

Final note

See this related PP&CG question.

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ @Giuseppe: this is not a duplicate. The other question isn't about the sequence itself, but a slice of the sequence ("the n first terms of the sequence are greater than n" to be exact). This is a more "pure sequence" version of the same sequence (and thus another challenge). By the way: sandboxed here. \$\endgroup\$ Commented Mar 10, 2019 at 18:46
  • 10
    \$\begingroup\$ Seems like for most, if not all, languages it would be a trivial change from counting greater than n to indexing into at n or tailing. For example Husk in the linked challenge is #>¹↑¡§ḟȯ←⌋→`-Nḣ2 and here !¡§ḟȯ←⌋→`-Nḣ2 would do (Try it). The definition of "duplicate" is not "is exactly the same as". I'll leave it to others to decide since I don't want to hammer this closed as I may have missed something. \$\endgroup\$ Commented Mar 10, 2019 at 19:15
  • 1
    \$\begingroup\$ Maybe you should specify that a(n) shares a factor other than 1 with a(n-1), since every number shares 1 as a factor. Also, may my answer be '2-indexed', where a(2) is 1, a(3) is 2, and so on? \$\endgroup\$ Commented Mar 11, 2019 at 3:34
  • 1
    \$\begingroup\$ This would be good for one fast code completion... \$\endgroup\$ Commented Mar 12, 2019 at 16:10

10 Answers 10

Reset to default
7
\$\begingroup\$

Haskell, 66 65 64 bytes

f n|n<3=n|m<-n-1=[k|k<-[1..],k`gcd`f m>1,all(/=k)$f<$>[1..m]]!!0

Try it online!

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Haskell, 60 bytes

((1:2#[3..])!!) n#l|x:_<-[y|y<-l,gcd y n>1]=n:x#filter(/=x)l

Try it online!

Zero-indexed; could save four bytes if series started with 2 (kinda (-1)-indexed, but without value for -1 being defined). Builds the infinite list by lazily maintaining the list of unused numbers.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Might be worth mentioning that you could make this considerably less inefficient if you import Data.List and use delete x instead of filter(/=x). If this needs to work for large arguments, such an optimization will quickly become necessary. \$\endgroup\$ Commented Mar 12, 2019 at 21:36
  • \$\begingroup\$ Indeed, using delete is the reasonable thing to do here, but in code-golf we don't care. I sometimes mention more efficient variants, when the difference is spectacular, or otherwise interesting. Here, it is not too bad: TIO can compute all test cases in less than 10 seconds. \$\endgroup\$ Commented Mar 12, 2019 at 22:55
4
\$\begingroup\$

Python 2, 104 bytes

This uses 0-based indexing.

from fractions import* l=[1,2] exec'i=3\nwhile gcd(i,l[-1])<2or i in l:i+=1\nl+=i,;'*input() print l[-2]

Try it online!

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

05AB1E, 25 bytes

1ˆ2ˆF∞.Δ¯yå≠¯θy¿2@*}ˆ}¯¨θ

0-indexed

Try it online or Output the first \$n\$ items.

Explanation:

1ˆ2ˆ # Add both 1 and 2 to the global_array F # Loop the (implicit) input amount of times: ∞.Δ # Get the first 1-indexed value resulting in truthy for the following: ¯yå≠ # Where this value is not in the global_array yet * # AND: ¯θ ¿ # Where the greatest common divisor of the last item of the global_array y @2 # and the current value, is larger than or equal to 2 }ˆ # After a new value has been found: add it to the global_array }¯ # After the loop: push the global_array ¨θ # Then remove the last element, and then take the new last element # (which is output implicitly as result)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby, 86 bytes

a=->(n){n<3?n:1.step{|i|return i if a[n-1].gcd(i)!=1&&(0...n).map(&a).all?{|j|j!=i}}}

This runs forever for inputs as low as 10, though.

Here's a version with memoization with 102 bytes that runs in acceptable time:

m={};a=->(n){n<3?n:m[n]||1.step{|i|return m[n]=i if a[n-1].gcd(i)!=1&&(0...n).map(&a).all?{|j|j!=i}}}
Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ can you save a byte with gcd >1 instead of !=1? \$\endgroup\$ Commented Mar 21, 2019 at 3:06
1
\$\begingroup\$

MACHINE LANGUAGE(X86, 32 bit)+C language library malloc()/free()functions, bytes 325

00000750 51 push ecx 00000751 52 push edx 00000752 8B44240C mov eax,[esp+0xc] 00000756 8B4C2410 mov ecx,[esp+0x10] 0000075A 3D00000000 cmp eax,0x0 0000075F 7414 jz 0x775 00000761 81F900000000 cmp ecx,0x0 00000767 740C jz 0x775 00000769 39C8 cmp eax,ecx 0000076B 7710 ja 0x77d 0000076D 89C2 mov edx,eax 0000076F 89C8 mov eax,ecx 00000771 89D1 mov ecx,edx 00000773 EB08 jmp short 0x77d 00000775 B8FFFFFFFF mov eax,0xffffffff 0000077A F9 stc 0000077B EB11 jmp short 0x78e 0000077D 31D2 xor edx,edx 0000077F F7F1 div ecx 00000781 89C8 mov eax,ecx 00000783 89D1 mov ecx,edx 00000785 81FA00000000 cmp edx,0x0 0000078B 77F0 ja 0x77d 0000078D F8 clc 0000078E 5A pop edx 0000078F 59 pop ecx 00000790 C20800 ret 0x8 00000793 53 push ebx 00000794 56 push esi 00000795 57 push edi 00000796 55 push ebp 00000797 55 push ebp 00000798 8B442418 mov eax,[esp+0x18] 0000079C 3D02000000 cmp eax,0x2 000007A1 7641 jna 0x7e4 000007A3 3DA0860100 cmp eax,0x186a0 000007A8 7757 ja 0x801 000007AA 40 inc eax 000007AB 89C7 mov edi,eax 000007AD C1E003 shl eax,0x3 000007B0 50 push eax 000007B1 E80E050000 call 0xcc4 000007B6 81C404000000 add esp,0x4 000007BC 3D00000000 cmp eax,0x0 000007C1 743E jz 0x801 000007C3 89C5 mov ebp,eax 000007C5 89F8 mov eax,edi 000007C7 C1E002 shl eax,0x2 000007CA 890424 mov [esp],eax 000007CD 50 push eax 000007CE E8F1040000 call 0xcc4 000007D3 81C404000000 add esp,0x4 000007D9 3D00000000 cmp eax,0x0 000007DE 7415 jz 0x7f5 000007E0 89C3 mov ebx,eax 000007E2 EB28 jmp short 0x80c 000007E4 E9A3000000 jmp 0x88c 000007E9 53 push ebx 000007EA E8E5040000 call 0xcd4 000007EF 81C404000000 add esp,0x4 000007F5 55 push ebp 000007F6 E8D9040000 call 0xcd4 000007FB 81C404000000 add esp,0x4 00000801 B8FFFFFFFF mov eax,0xffffffff 00000806 F9 stc 00000807 E981000000 jmp 0x88d 0000080C C60301 mov byte [ebx],0x1 0000080F C6430101 mov byte [ebx+0x1],0x1 00000813 C7450001000000 mov dword [ebp+0x0],0x1 0000081A C7450402000000 mov dword [ebp+0x4],0x2 00000821 B902000000 mov ecx,0x2 00000826 BE01000000 mov esi,0x1 0000082B B802000000 mov eax,0x2 00000830 8B542418 mov edx,[esp+0x18] 00000834 4A dec edx 00000835 C6040300 mov byte [ebx+eax],0x0 00000839 40 inc eax 0000083A 3B0424 cmp eax,[esp] 0000083D 72F6 jc 0x835 0000083F BF02000000 mov edi,0x2 00000844 81C701000000 add edi,0x1 0000084A 3B3C24 cmp edi,[esp] 0000084D 779A ja 0x7e9 0000084F 803C3B01 cmp byte [ebx+edi],0x1 00000853 74EF jz 0x844 00000855 57 push edi 00000856 51 push ecx 00000857 E8F4FEFFFF call 0x750 0000085C 3D01000000 cmp eax,0x1 00000861 76E1 jna 0x844 00000863 46 inc esi 00000864 897CB500 mov [ebp+esi*4+0x0],edi 00000868 89F9 mov ecx,edi 0000086A C6043B01 mov byte [ebx+edi],0x1 0000086E 39D6 cmp esi,edx 00000870 72CD jc 0x83f 00000872 53 push ebx 00000873 E85C040000 call 0xcd4 00000878 81C404000000 add esp,0x4 0000087E 55 push ebp 0000087F E850040000 call 0xcd4 00000884 81C404000000 add esp,0x4 0000088A 89F8 mov eax,edi 0000088C F8 clc 0000088D 5D pop ebp 0000088E 5D pop ebp 0000088F 5F pop edi 00000890 5E pop esi 00000891 5B pop ebx 00000892 C20400 ret 0x4 00000895

Above gcd and the function... This below assembly code generate the functions and the test program:

; nasmw -fobj this.asm ; bcc32 -v this.obj section _DATA use32 public class=DATA global _main extern _printf extern _malloc extern _free dspace dd 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 fmt db "%u " , 13, 10, 0, 0 fmt1 db "%u %u" , 13, 10, 0, 0 IgcdIIuIIIuIIIuIn db "gcd(%u, %u)=%u" , 13, 10, 0, 0 IfunIIuIIIuIn db "fun(%u)=%u" , 13, 10, 0, 0 section _TEXT use32 public class=CODE gcd: push ecx push edx mov eax, dword[esp+ 12] mov ecx, dword[esp+ 16] cmp eax, 0 je .e cmp ecx, 0 je .e cmp eax, ecx ja .1 mov edx, eax mov eax, ecx mov ecx, edx jmp short .1 .e: mov eax, -1 stc jmp short .z .1: xor edx, edx div ecx mov eax, ecx mov ecx, edx cmp edx, 0 ja .1 ; r<c .2: clc .z: pop edx pop ecx ret 8 fun: push ebx push esi push edi push ebp push ebp mov eax, dword[esp+ 24] cmp eax, 2 jbe .a cmp eax, 100000 ja .e inc eax mov edi, eax shl eax, 3 push eax call _malloc add esp, 4 cmp eax, 0 je .e mov ebp, eax mov eax, edi shl eax, 2 mov dword[esp+ 0], eax push eax call _malloc add esp, 4 cmp eax, 0 je .0 mov ebx, eax jmp short .1 .a: jmp .y .b: push ebx call _free add esp, 4 .0: push ebp call _free add esp, 4 .e: mov eax, -1 stc jmp .z .1: mov byte[ebx], 1 mov byte[ebx+1], 1 mov dword[ebp], 1 mov dword[ebp+4], 2 mov ecx, 2 mov esi, 1 mov eax, 2 mov edx, dword[esp+ 24] dec edx .2: mov byte[ebx+eax], 0 inc eax cmp eax, dword[esp+ 0] jb .2 .3: mov edi, 2 .4: add edi, 1 cmp edi, dword[esp+ 0] ja .b cmp byte[ebx+edi], 1 je .4 push edi push ecx call gcd cmp eax, 1 jbe .4 inc esi mov [ebp+esi*4], edi mov ecx, edi mov byte[ebx+edi], 1 cmp esi, edx jb .3 push ebx call _free add esp, 4 push ebp call _free add esp, 4 mov eax, edi .y: clc .z: pop ebp pop ebp pop edi pop esi pop ebx ret 4 _main: pushad push 6 push 3 call gcd pushad push eax push 6 push 3 push IgcdIIuIIIuIIIuIn call _printf add esp, 16 popad push 2 push 2 call gcd pushad push eax push 2 push 2 push IgcdIIuIIIuIIIuIn call _printf add esp, 16 popad push 1 push 1 call gcd pushad push eax push 1 push 1 push IgcdIIuIIIuIIIuIn call _printf add esp, 16 popad push 0 push 1 call gcd pushad push eax push 0 push 1 push IgcdIIuIIIuIIIuIn call _printf add esp, 16 popad push 0 call fun pushad push eax push 0 push IfunIIuIIIuIn call _printf add esp, 12 popad push 1 call fun pushadpush eax push 1 push IfunIIuIIIuIn call _printf add esp, 12 popad push 2 call fun pushad push eax push 2 push IfunIIuIIIuIn call _printf add esp, 12 popad push 3 call fun pushad push eax push 3 push IfunIIuIIIuIn call _printf add esp, 12 popad push 4 call fun pushad push eax push 4 push IfunIIuIIIuIn call _printf add esp, 12 popad push 5 call fun pushad push eax push 5 push IfunIIuIIIuIn call _printf add esp, 12 popad push 123 call fun pushad push eax push 123 push IfunIIuIIIuIn call _printf add esp, 12 popad push 1234 call fun pushad push eax push 1234 push IfunIIuIIIuIn call _printf add esp, 12 popad push 3000 call fun pushad push eax push 3000 push IfunIIuIIIuIn call _printf add esp, 12 popad push 9999 call fun pushad push eax push 9999 push IfunIIuIIIuIn call _printf add esp, 12 popad push 99999 call fun pushad push eax push 99999 push IfunIIuIIIuIn call _printf add esp, 12 popad popad mov eax, 0 ret

the results:

gcd(3, 6)=3 gcd(2, 2)=2 gcd(1, 1)=1 gcd(1, 0)=4294967295 fun(0)=0 fun(1)=1 fun(2)=2 fun(3)=4 fun(4)=6 fun(5)=3 fun(123)=132 fun(1234)=1296 fun(3000)=3122 fun(9999)=10374 fun(99999)=102709

It is possible bugs and wrong copy past...

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl 6, 84 80 73 69 50 49 bytes

(0-indexed)

{(1,2,{+(1...all @_[*-1]gcd*>1,*∉@_)}...*)[$_]}

Thanks to this answer for some tricks.

Thanks to ASCII-only for shaving a byte.

Improve this answer
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Have you tried using the sequence operator ...? It makes sequence stuff like this a lot easier. For example, your my@a=1,2;push @a,operation while condition can be 1,2,{operation}...condition. With a few other golfs, this can be as low as 49 bytes \$\endgroup\$ Commented Mar 21, 2019 at 3:37
  • \$\begingroup\$ Not sure if that'd work here because the next term depends on all of the previous terms. \$\endgroup\$ Commented Mar 21, 2019 at 5:18
  • \$\begingroup\$ 67 (0-indexing is allowed though, so this could be 65) \$\endgroup\$ Commented Mar 21, 2019 at 5:38
  • \$\begingroup\$ Derp, didn't come to my mind that there was .first. \$\endgroup\$ Commented Mar 21, 2019 at 5:39
  • 1
    \$\begingroup\$ O_o well that was a big jump. it'd be nice if you could link to TIO though \$\endgroup\$ Commented Mar 21, 2019 at 5:44
0
\$\begingroup\$

APL(NARS), chars 119, bytes 238

∇r←a w;i;j;v r←w⋄→0×⍳w≤2⋄i←2⋄r←⍳2⋄v←1,1,(2×w)⍴0 j←¯1+v⍳0 j+←1⋄→3×⍳1=j⊃v⋄→3×⍳∼1<j∨i⊃r⋄r←r,j⋄i+←1⋄v[j]←1⋄→2×⍳w>i r←i⊃r ∇

this test it takes 1m:49s here:

 a¨1 5 20 50 123 1234 3000 1 3 11 49 132 1296 3122
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Java (JDK), 161 155 152 151 bytes

Saved a byte by switching int[] tracking to leverage the existing BigInteger!

n->{int j,k=n;for(var b=java.math.BigInteger.ONE;0<--n;b=b.setBit(k=j))for(j=1;b.testBit(++j)|b.valueOf(j).gcd(b.valueOf(k)).intValue()<2;);;return k;}

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Gaia, 27 bytes

2┅@⟨:1⟪Ė₌0⟪;)d;d&1D⟫?⟫#+⟩ₓE

Try it online!

1-based indexing.

Runs rather slowly, as it tries each integer until it finds a(n).

2┅				| push [1 2] @				| push n ⟨			 ⟩ₓ	| do n times: :				| dup 1⟪		 ⟫#	| and find the first 1 integer i where the following results in a truthy value: Ė₌	 ?		| is i an Ėlement of the list? Also push an extra copy of the arguments 	 0			| if so, give falsy result, so try the next integer 	 ⟪	 ⟫		| else do the following: 	 ;)d			| get divisors of a(n-1) 	 ;d		| get divisors of i 		&1D		| set intersect and remove the first element (which is always 1) 				| this yields an empty set if no divisors are shared (falsy, so try next integer) 				| or a non-empty set (truthy, so returns i = a(n)) 			+	| and concatenate to list (end loop). 			 E	| finally, Extract the nth element (n taken implicitly)
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.