Dapatkah cincin pohon persegi dihasilkan dari bilangan prima?

33

Ternyata iya! Dalam tiga langkah mudah.

Langkah 1

Misalkan f ( n ) menunjukkan fungsi penghitungan prime (jumlah bilangan prima kurang dari atau sama dengan n ).

Tentukan urutan bilangan bulat s ( n ) sebagai berikut. Untuk setiap bilangan bulat positif n ,

  • Prakarsai t ke n .
  • Selama t bukan prima atau 1, ganti t dengan f ( t ) dan iterate.
  • Jumlah iterasi adalah s ( n ).

Proses berulang dijamin berakhir karena f ( n ) < n untuk semua n .

Pertimbangkan misalnya n = 25. Kami memulai semua t = 25. Karena ini bukan bilangan prima atau 1, kami menghitung f (25), yaitu 9. Ini menjadi nilai baru untuk t . Ini bukan prima atau 1, jadi kami melanjutkan: f (9) adalah 4. Kami melanjutkan lagi: f (4) adalah 2. Karena ini adalah prima, kami berhenti di sini. Kami telah melakukan 3 iterasi (dari 25 menjadi 9, lalu ke 4, lalu ke 2). Jadi s (25) adalah 3.

40 syarat pertama dari urutan adalah sebagai berikut. Urutannya bukan di OEIS.

0 0 0 1 0 1 0 2 2 2 0 1 0 2 2 2 0 1 0 3 3 3 0 3 3 3 3 3 0 3 0 1 1 1 1 1 0 2 2 2

Langkah 2

Mengingat positif aneh bilangan bulat N , membangun sebuah array N × N (matriks) dengan menggulungnya urutan terbatas s (1), s (2), ..., s ( N 2 ) untuk membentuk persegi luar spiral . Sebagai contoh, diberikan N = 5 spiral adalah

s(21)   s(22)   s(23)   s(24)   s(25)
s(20)   s(7)    s(8)    s(9)    s(10)
s(19)   s(6)    s(1)    s(2)    s(11)
s(18)   s(5)    s(4)    s(3)    s(12)
s(17)   s(16)   s(15)   s(14)   s(13)

atau, menggantikan nilai-nilai,

 3       3       0       3       3
 3       0       2       2       2
 0       1       0       0       0
 1       0       1       0       1
 0       2       2       2       0

Langkah 3

Mewakili susunan N × N sebagai gambar dengan peta warna abu-abu, atau dengan beberapa peta warna lain sesuai selera Anda. Peta harus bertahap, sehingga urutan angka sesuai dengan urutan warna yang terlihat jelas. Kasus uji di bawah ini menunjukkan beberapa contoh peta warna.

Tantangan

Mengingat positif aneh bilangan bulat N , menghasilkan gambar yang dijelaskan di atas.

Aturan

  • Spiral harus keluar, tetapi bisa searah atau berlawanan arah jarum jam, dan dapat mulai bergerak ke kanan (seperti dalam contoh di atas), kiri, bawah atau atas.

  • Timbangan sumbu horizontal dan vertikal tidak harus sama. Label sumbu, bilah warna, dan elemen serupa juga opsional. Selama spiral dapat dilihat dengan jelas, gambar tersebut valid.

  • Gambar dapat dihasilkan dengan salah satu cara standar . Secara khusus, gambar dapat ditampilkan di layar, atau file grafik dapat diproduksi, atau array nilai RGB dapat dihasilkan. Jika menghasilkan file atau array, silakan posting contoh seperti apa saat ditampilkan.

  • Sarana input dan format fleksibel seperti biasa . Sebuah program atau fungsi dapat disediakan . Celah standar dilarang .

  • Kode terpendek dalam byte menang.

Uji kasus

Gambar berikut (klik untuk resolusi penuh) sesuai dengan beberapa nilai dari N . Spiral jam, spiral ke kanan pertama digunakan, seperti pada contoh di atas. Gambar juga menggambarkan beberapa peta warna yang valid.

  • N = 301: masukkan deskripsi gambar di sini

  • N = 501: masukkan deskripsi gambar di sini

  • N = 701: masukkan deskripsi gambar di sini

Luis Mendo
sumber
Jika sebuah array nilai-nilai s(n)dapat dimasukkan ke dalam beberapa fungsi fungsi / paket tanpa dimodifikasi (saya pikir imshowdalam matplotlib dapat menangani ini misalnya) apakah ini bentuk output yang dapat diterima?
dylnan
@dylnan Tentu, selama itu memplot gambar di layar atau menghasilkan file itu valid. Sebenarnya saya membuat contoh dengan sesuatu yang mirip dengan apa yang Anda sebutkan. Berhati-hatilah dengan penskalaan nilai. Sebagai contoh itu tidak dapat diterima jika semua nilai di atas 1 diberikan warna yang sama, seperti Matlab (dan mungkin Matplotlib ini) imshowtidak
Luis Mendo
poin yang bagus. Tidak yakin apakah imshowitu.
dylnan
1
@ kamoroso94 Silakan lihat di sini
Luis Mendo
1
Ya sangat jelas
Christopher

Jawaban:

3

Dyalog APL, 94 byte

'P2'
2⍴n←⎕
9
(⍪0){×≢⍵:(≢⍺)((⍉∘⌽⍺,↑)∇↓)⍵⋄⍺}2↓{⍵⌊1+⍵[+\p]}⍣≡9×~p←1=⊃+/(≠⍨,≠⍨,~⍴⍨(×⍨n)-2×≢)¨,\×⍳n

mengasumsikan ⎕IO=0

output untuk n = 701 (dikonversi dari .pgm ke .png):

masukkan deskripsi gambar di sini

ngn
sumber
10

MATLAB - 197 185 178 175 184 163 162 148 142 140 byte

Mencukur 12 byte, terima kasih kepada Ander dan Andras, dan terima kasih banyak kepada Luis karena telah menyatukan keduanya. Bercukur 16 berkat Remco, 6 berkat flawr

function F(n)
p=@primes
s=@isprime
for a=2:n^2
c=0
if~s(a)
b=nnz(p(a))
while~s(b)
b=nnz(p(b))
c=c+1
end
end
d(a)=c
end
imagesc(d(spiral(n)))

Hasil untuk N=301( F(301)):

masukkan deskripsi gambar di sini

Penjelasan:

function F(n)
p=@primes % Handle
s=@isprime % Handle
for a=2:n^2 % Loop over all numbers
    c=0 % Set initial count
    if~s(a) % If not a prime
        b=nnz(p(a)) % Count primes
        while~s(b) % Stop if b is a prime. Since the code starts at 2, it never reaches 1 anyway
            b=nnz(p(b)) % count again
            c=c+1 % increase count
        end
    end
    d(a)=c % store count
end
imagesc(d(spiral(n))) % plot
Adriaan
sumber
8

Bahasa Wolfram (Mathematica) , 124 byte

Terima kasih kepada Martin Ender untuk menghemat 12 byte!

Image[#/Max@#]&[Array[(n=0;Max[4#2#2-Max[+##,3#2-#],4#
#-{+##,3#-#2}]+1//.x_?CompositeQ:>PrimePi[++n;x];n)&,{#,#},(1-#)/2]]&

Cobalah online!


Gambar yang dihasilkan adalah:

Spiral

Formula bentuk tertutup dari nilai spiral yang diambil langsung dari jawaban saya ini.

pengguna202729
sumber
5
#/2-.5menghemat satu byte.
user202729
8
Haha, apakah Anda menyarankan itu pada diri sendiri?
Luis Mendo
6
@ user202729 Sepertinya tidak berfungsi.
user202729
18
Saya tidak bermaksud mengganggu dialog batin Anda :-P
Luis Mendo
Tunda definisi phingga Anda membutuhkannya:...,{y,p=(1-#)/2,-p},{x,p,-p}
Martin Ender
7

MATLAB: 115 114 110 byte

Satu liner (berjalan di R2016b + sebagai fungsi dalam skrip ) 115 byte

I=@(N)imagesc(arrayfun(@(x)s(x,0),spiral(N)));function k=s(n,k);if n>1&~isprime(n);k=s(nnz(primes(n)),k+1);end;end

Menempatkan fungsi dalam file terpisah, seperti yang disarankan oleh flawr, dan menggunakan 1 byte tambahan per aturan file tambahan

Dalam file tersebut s.m, 64 +1 byte untuk kode + file

function k=s(n,k);if n>1&~isprime(n);k=s(nnz(primes(n)),k+1);end

Jendela perintah untuk didefinisikan I, 45 byte

I=@(N)imagesc(arrayfun(@(x)s(x,0),spiral(N)))

Total: 110 byte


Ini menggunakan rekursi alih-alih whileperulangan seperti implementasi MATLAB lainnya ( gnovice , Adriaan ). Jalankan sebagai skrip (dalam R2016b atau lebih baru), ini mendefinisikan fungsi Iyang dapat dijalankan seperti I(n).

Versi terstruktur:

% Anonymous function for use, i.e. I(301)
% Uses arrayfun to avoid for loop, spiral to create spiral!
I=@(N)imagesc(arrayfun(@(x)s(x,0),spiral(N)));

% Function for recursively calculating the s(n) value
function k=s(n,k)
    % Condition for re-iterating. Otherwise return k unchanged
    if n>1 && ~isprime(n)
        % Increment k and re-iterate
        k = s( nnz(primes(n)), k+1 );
    end
end

Contoh:

I(301)

merencanakan

Catatan:

  • Saya mencoba membuat sfungsi anonim juga, tentu saja itu akan mengurangi jumlah secara signifikan. Namun, ada 2 masalah:

    1. Rekursi tak terbatas sulit untuk dihindari ketika menggunakan fungsi anonim, karena MATLAB tidak memiliki operator ternary untuk menawarkan kondisi istirahat. Membentuk operator ternary semacam (lihat di bawah) juga biaya byte karena kita membutuhkan kondisi dua kali.

    2. Anda harus meneruskan fungsi anonim ke dirinya sendiri jika bersifat rekursif (lihat di sini ) yang menambahkan byte.

    Yang paling dekat saya dengan ini menggunakan baris berikut, mungkin dapat diubah untuk bekerja:

    % Condition, since we need to use it twice 
    c=@(n)n>1&&~isprime(n);
    % This uses a bodged ternary operator, multiplying the two possible outputs by
    % c(n) and ~c(n) and adding to return effectively only one of them
    % An attempt was made to use &&'s short-circuiting to avoid infinite recursion
    % but this doesn't seem to work!
    S=@(S,n,k)~c(n)*k+c(n)&&S(S,nnz(primes(n)),k+1);
Wolfie
sumber
6

MATLAB - 126 121 * byte

Saya mencoba pendekatan yang lebih vektor daripada Adriaan dan mampu mencukur lebih banyak byte. Inilah solusi single-line:

function t(n),M=1:n^2;c=0;i=1;s=@isprime;v=cumsum(s(M));while any(i),i=M>1&~s(M);c=c+i;M(i)=v(M(i));end;imagesc(c(spiral(n)))

Dan inilah solusi yang diformat dengan baik:

function t(n),
  M = 1:n^2;
  c = 0;
  i = 1;
  s = @isprime;
  v = cumsum(s(M));
  while any(i),         % *See below
    i = M > 1 & ~s(M);
    c = c+i;
    M(i) = v(M(i));
  end;
  imagesc(c(spiral(n)))

* Catatan: jika Anda bersedia untuk memungkinkan crapton metrik iterasi yang tidak perlu, Anda dapat mengubah baris while any(i), ke for m=v, dan Hemat 5 byte.

gnovice
sumber
Bagus! Saya suka bagaimana Anda menggunakannya cumsumuntuk membuat vektor dan menghindarinnz(primes(...)
Luis Mendo
1
Jika saya mengerti dengan benar, tidak ada salahnya untuk mengulang lebih dari yang diperlukan (dengan mengorbankan kecepatan). Jadi Anda bisa menggantinya while any(i)dengan for m=M. Siapa yang peduli jika kode ini membutuhkan waktu berjam-jam untuk berjalan :-)
Luis Mendo
2
@LuisMendo: Tentu, mengapa tidak? Sudah mengulangi sekali lagi dari yang dibutuhkan, apa lagi n^2atau tidaknya iterasi akan terasa sakit! ;)
gnovice
1
Itulah semangat! Anda juga dapat mempertahankan versi yang berjalan lebih cepat, tetapi jumlah byte lebih pendek
Luis Mendo
2

Python 3, 299 265 byte

Disimpan 5 byte berkat memformat saran dari Jonathan Frech dan NoOneIsHere. Menghapus 34 byte tambahan dengan menghapus definisi fungsi yang hanya dipanggil sekali.

Ini sedikit lebih lama daripada yang lain, karena python tidak memiliki perintah untuk menentukan primeness, atau spiral array. Namun berjalan relatif cepat, sekitar satu menit n = 700.

from pylab import*
def S(n):
 q=arange(n*n+1);t=ones_like(q)
 for i in q[2:]:t[2*i::i]=0
 c=lambda i:0 if t[i]else 1+c(sum(t[2:i]));S=[c(x)for x in q]
 t=r_[[[S[1]]]]
 while any(array(t.shape)<n):m=t.shape;i=multiply(*m)+1;t=vstack([S[i:i+m[0]],rot90(t)])
 return t

Uji dengan

n = 7
x = S(n)
imshow(x, interpolation='none')
colorbar()
show(block=False)
pengguna2699
sumber
1
Kemungkinan 294 byte (belum diuji).
Jonathan Frech
1
Satu hal cepat: Anda dapat menghapus ruang antara importdan *.
NoOneIsHere
2

J, 121 Bytes

load 'viewmat'
a=:3 :'viewmat{:@((p:inv@{.,>:@{:)^:(-.@((=1:)+.1&p:)@{.)^:_)@(,0:)"0(,1+(i.@#+>./)@{:)@|:@|.^:(+:<:y),.1'

Mendefinisikan suatu fungsi:

a=:3 :'viewmat{:@((p:inv@{.,>:@{:)^:(-.@((=1:)+.1&p:)@{.)^:_)@(,0:)"0(,1+(i.@#+>./)@{:)@|:@|.^:(+:<:y),.1' | Full fuction
                                                                     (,1+(i.@#+>./)@{:)@|:@|.^:(+:<:y),.1  | Creates the number spiral
              {:@((p:inv@{.,>:@{:)^:(-.@((=1:)+.1&p:)@{.)^:_)@(,0:)"0                                      | Applies S(n) to each element
       viewmat                                                                                             | View the array as an image
Bolce Bussiere
sumber
2

R, 231 byte

function(n){p=function(n)sum(!n%%2:n)<2;M=matrix(0,n,n);M[n^2%/%2+cumsum(c(1,head(rep(rep(c(1,-n,-1,n),l=2*n-1),rev(n-seq(n*2-1)%/%2)),-1)))]=sapply(1:(n^2),function(x){y=0;while(x>2&!p(x)){x=sum(sapply(2:x,p));y=y+1};y});image(M)}

Sedikit kurang golf:

function(n){
    p=function(n)sum(!n%%2:n)<2 #"is.prime" function
    M=matrix(0,n,n)             #empty matrix
    indices=n^2%/%2+cumsum(c(1,head(rep(rep(c(1,-n,-1,n),l=2*n-1),rev(n-seq(n*2-1)%/%2)),-1)))
    values=sapply(1:(n^2),function(x){
        y=0
        while(x>2&!p(x)){
            x=sum(sapply(2:x,p))
            y=y+1
            }
        y})
    M[indices]=values
    image(M) #Plotting
}

Fungsi anonim. Keluaran dalam jendela grafis. Skala berada pada skala merah dengan naungan tergelap sama dengan 0 dan nilai yang lebih jelas meningkatkan nuansa.

Hasil untuk n = 101:

n = 101

plannapus
sumber