Carl Love

Carl Love

28055 Reputation

25 Badges

12 years, 358 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

What size n are you interested in expressing as a sum of 4 squares? The algorithm that I gave below works reasonably efficiently (say, <= 16 milliseconds) for of many hundreds of bits. It may get bogged down if n has two or more large, distinct prime factors on the order of, say, a hundred bits. This slowness is just due to finding the prime factorization of n. If you need to work with such n, I'll implement the Rabin & Shallit algorithm (from the paper mentioned below), which doesn't use the prime factorization of and has average time complexity O(log(n)^2*log(log(n))).

Yes, it's easy. What do you want to be the time parameter of the animation--perhaps the standard deviation? You'd likely get better pedagogy---if that's your purpose---from an Explore command than from a dedicated animation.

@vv Yes, that's the paper that I was looking for. Thank you for posting it.

When I first read this Post, I quickly suspected that the order of the permutation would be a fairly easy closed-form function of its length and that the number of disjoint cycles would be small regardless of  length; however, neither of those seem to be true. Given that, it would seem odd that Order(P(n)) <= n for all n. Has someone proven that? Below, I've verified it up to n=4096.

Here are some explorations:

Some explorations viewing the Arabic Cipher as a permutation

Author: Carl Love <carl.j.love@gmail.com> 19-Sep-2019

restart
:

Procedures

#Create Arabic Cipher permutation:
ACperm:= (n::posint)->
   (h-> ListTools:-Interleave(
      `if`(n::odd, [-[$-h-1..-1], [$h+2..n]], [[$h+1..n], -[$-h..-1]])[]
   ))(iquo(n,2))
:

#Apply Cipher to a string:
ACapply:= (s::string)-> StringTools:-Permute(s, ACperm(length(s))):

#order of the permutation:
ACorder:= (n::posint)-> ilcm(nops~(convert(ACperm(n), 'disjcyc'))[]):
#number of disjoint cycles in the permutation:
ACndjc:= (n::posint)-> nops(convert(ACperm(n), 'disjcyc')):

Examples

ACperm(14);

[8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1]

ACapply("AlbertEinstein");

"iEntsrteebilnA"

ACorder(14);

14

ACndjc(14);

1

seq([n, ACndjc(n)], n= 1..16);

[1, 0], [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 2], [8, 2], [9, 1], [10, 2], [11, 1], [12, 2], [13, 2], [14, 1], [15, 3], [16, 3]

Plots

N:= 2..2^12: #range of string lengths
plotopts:=
   style= point, symbol= solidcircle, symbolsize= 3, gridlines= false,
   color= "Bright ReddishPurple", size= [800,500], axes= frame
:

Orders:= [seq([n, ACorder(n)], n= N)]:

plot(Orders, plotopts, title= "Order vs. Length");

The above looks interesting from a number-theoretical perspective. What forms the lines? (I'll leave that question aside for now.) Also note that the order is always less than or equal to the length.

plot(
   `[]`~(ListTools:-Enumerate((`/`@op)~(Orders))), plotopts,
   symbolsize= (trunc@(1+log[2])@`/`@op)~(Orders),
   title= "Length/Order vs. Length"
);

Ndjc:= ACndjc~([$N]):

plot(
   `[]`~(ListTools:-Enumerate(Ndjc)), plotopts,
   symbolsize= (trunc@(1+log[2]))~(Ndjc),
   title= "Number of disjoint cycles vs. Length"
);

The above two plots are oddly similar, yet definitely different. The disjoint-cycles-vs-length looks statistically interesting.

The data in the two lists below is the same, just sorted differently. The left side of each equation is a number of disjoint cycles and the right side is the number of distinct lengths for which that number of cycles was attained.  

NLvsNdjc:= Statistics:-Tally(Ndjc):

NLvsNdjc__byNdjc:= sort(NLvsNdjc, key= [lhs,rhs]);

[1 = 590, 2 = 275, 3 = 489, 4 = 233, 5 = 217, 6 = 190, 7 = 232, 8 = 169, 9 = 145, 10 = 74, 11 = 93, 12 = 109, 13 = 114, 14 = 81, 15 = 44, 16 = 59, 17 = 48, 18 = 50, 19 = 54, 20 = 58, 21 = 39, 22 = 54, 23 = 42, 24 = 20, 25 = 23, 26 = 16, 27 = 19, 28 = 20, 29 = 32, 30 = 19, 31 = 26, 32 = 32, 33 = 24, 34 = 19, 35 = 9, 36 = 17, 37 = 11, 38 = 12, 39 = 5, 40 = 10, 41 = 13, 42 = 18, 43 = 15, 44 = 6, 45 = 6, 46 = 12, 47 = 3, 48 = 16, 49 = 7, 50 = 5, 51 = 2, 52 = 8, 53 = 8, 54 = 14, 55 = 4, 56 = 8, 57 = 12, 58 = 5, 59 = 3, 60 = 4, 62 = 11, 63 = 9, 64 = 3, 66 = 3, 67 = 3, 68 = 3, 69 = 1, 70 = 4, 71 = 7, 72 = 9, 73 = 3, 74 = 3, 76 = 4, 78 = 2, 79 = 2, 80 = 1, 81 = 2, 82 = 4, 83 = 1, 84 = 1, 85 = 1, 86 = 2, 88 = 5, 89 = 1, 90 = 3, 91 = 1, 92 = 1, 93 = 3, 94 = 1, 95 = 1, 96 = 2, 98 = 1, 100 = 2, 102 = 1, 104 = 2, 105 = 4, 106 = 2, 107 = 1, 111 = 2, 112 = 3, 114 = 1, 115 = 1, 117 = 4, 118 = 3, 119 = 2, 122 = 1, 123 = 2, 129 = 1, 130 = 1, 134 = 2, 142 = 1, 146 = 2, 147 = 1, 155 = 1, 156 = 2, 158 = 2, 161 = 1, 167 = 1, 172 = 1, 178 = 2, 179 = 1, 186 = 1, 201 = 2, 315 = 2]

NLvsNdjc_byNL:= sort(NLvsNdjc, key= [rhs,lhs]);

[69 = 1, 80 = 1, 83 = 1, 84 = 1, 85 = 1, 89 = 1, 91 = 1, 92 = 1, 94 = 1, 95 = 1, 98 = 1, 102 = 1, 107 = 1, 114 = 1, 115 = 1, 122 = 1, 129 = 1, 130 = 1, 142 = 1, 147 = 1, 155 = 1, 161 = 1, 167 = 1, 172 = 1, 179 = 1, 186 = 1, 51 = 2, 78 = 2, 79 = 2, 81 = 2, 86 = 2, 96 = 2, 100 = 2, 104 = 2, 106 = 2, 111 = 2, 119 = 2, 123 = 2, 134 = 2, 146 = 2, 156 = 2, 158 = 2, 178 = 2, 201 = 2, 315 = 2, 47 = 3, 59 = 3, 64 = 3, 66 = 3, 67 = 3, 68 = 3, 73 = 3, 74 = 3, 90 = 3, 93 = 3, 112 = 3, 118 = 3, 55 = 4, 60 = 4, 70 = 4, 76 = 4, 82 = 4, 105 = 4, 117 = 4, 39 = 5, 50 = 5, 58 = 5, 88 = 5, 44 = 6, 45 = 6, 49 = 7, 71 = 7, 52 = 8, 53 = 8, 56 = 8, 35 = 9, 63 = 9, 72 = 9, 40 = 10, 37 = 11, 62 = 11, 38 = 12, 46 = 12, 57 = 12, 41 = 13, 54 = 14, 43 = 15, 26 = 16, 48 = 16, 36 = 17, 42 = 18, 27 = 19, 30 = 19, 34 = 19, 24 = 20, 28 = 20, 25 = 23, 33 = 24, 31 = 26, 29 = 32, 32 = 32, 21 = 39, 23 = 42, 15 = 44, 17 = 48, 18 = 50, 19 = 54, 22 = 54, 20 = 58, 16 = 59, 10 = 74, 14 = 81, 11 = 93, 12 = 109, 13 = 114, 9 = 145, 8 = 169, 6 = 190, 5 = 217, 7 = 232, 4 = 233, 2 = 275, 3 = 489, 1 = 590]

plot(
   [[lhs,rhs]]~(NLvsNdjc), plotopts, axis[1,2]= [mode= log],
   symbolsize= (trunc@(1+log[2])@rhs)~(NLvsNdjc),
   title= "log(Attainments) vs. log(Number of disjoint cycles)"
);

Statistics:-Histogram(Ndjc, axes= frame, gridlines= false);

 


 

Download ArabicCipher.mw

  

I suppose the problem could be done in Maple. Matlab's fminsearch seems equivalent to parts of Maple's third-party DirectSearch package. I need details of "Pareto front" to proceed.

@Masooma I am happy to help further if you is still need it. Newton's method and its variations are an area of expertise of mine. I still don't see any merit to your method x-> x - 2*f(x)/D(f)(x) whether for ordinary or repeated roots.

It wouldn't let me attach the worksheet above. Here it is:
 

Generating random samples of primes uniformly from an interval

Author: Carl Love <carl.j.love@gmail.com>, 16 Sep 2019

:
restart
:

Method 1 (easy): This is a commonly used method for generating random primes; however, we shall see that it's far from uniform: Generate an integer uniformly from the interval (taking for granted that the basic rand is uniform) and then find the first prime greater than it.

EasyRandPrime:= (R::range(And(realcons, positive)))->
   nextprime@rand(ceil(lhs(R))-1 .. prevprime(floor(rhs(R)))-1)
:

Specify an interval to sample from:

intv:= 2^(2^7-1)..2^(2^7): #interval of 128-bit integers
:

Just like with regular rand, generating a sample is a two-step process: First create a generator, ...

ERP:= EasyRandPrime(intv):

... and then call it:

ERP();

277236106278070479859868052593834139529

The reason for using a two-step process is that when generating multiple primes from the same interval, the generator only needs to be created once.

 

Method 2 (uniform): Generate integers uniformly from the interval. Return the first of these that is prime.

#This syntax requires Maple 2018 or later:
UniformRandPrime:= proc(R::range(And(realcons, positive)))
local RI:= rand(ceil(lhs(R)) .. floor(rhs(R)));
   proc() local r; do r:= RI() until isprime(r) end proc
end proc
:

URP:= UniformRandPrime(intv):

URP();

254100590822665913645679870921325282759

Now I'll give some empirical evidence of uniformity. First, we approximate the number of primes in the interval using a well-known formula:

np:= evalf(Int(1/ln(x), x= intv));

0.1924335654e37

That computation can also be done using the special mathematical function Li: 

evalf(Li(rhs(intv)) - Li(lhs(intv)));

0.1924335653e37

So, there are approximately 2*10^36  primes in this interval. Clearly, it would be impossible to generate them all. Yet, they can be sampled uniformly. Let's calculate the mean spacing between consecutive primes in this interval:

spacing:= (rhs-lhs)(intv)/np;

88.41554390

Generate a moderately large sample, and time it:

N:= 2^12;

4096

P_uniform:= CodeTools:-Usage([seq(URP(), 1..N)]):

memory used=0.76GiB, alloc change=45.00MiB, cpu time=5.56s, real time=5.14s, gc time=1.14s

Compute the mean distance from each sampled prime to its predecessor:

#mean and relative standard deviation:
Stats:= (Statistics:-Mean, Statistics:-StandardDeviation/Statistics:-Mean)
:
Stats(P_uniform -~ prevprime~(P_uniform));

HFloat(91.166015625), HFloat(0.960583194915546)

And the mean distance from each to its successor:

Stats(nextprime~(P_uniform) -~ P_uniform);

HFloat(88.9853515625), HFloat(0.9636494347540869)

Average the above two means:

(%[1] + %%[1])/2;

HFloat(90.07568359375)

So, that is very close to the overall spacing.

 

Now do the same with the easy generator:

P_easy:= CodeTools:-Usage([seq(ERP(), 1..N)]):

memory used=0.63GiB, alloc change=0 bytes, cpu time=4.58s, real time=4.29s, gc time=906.25ms

We see that the easy generator is a little bit faster. Let's check its spacing:

Stats(P_easy -~ prevprime~(P_easy));

HFloat(170.06494140625), HFloat(0.6986022285672084)

Stats(nextprime~(P_easy) -~ P_easy);

HFloat(87.0791015625), HFloat(0.9481953557364504)

We see that the easy generator is heavily biased towards primes that are at greater distances from their predecessors. This bias would be difficult to detect with standard statistical tests; the histograms superficially show uniformity:

plots:-display(
   `<|>`(Statistics:-Histogram~([P_uniform, P_easy])[]),
   tickmarks= [[],[]]
):

 


The histograms can be generated in the worksheet. There's some trouble with uploading them directly.

Download UniformRandPrime.mw

The error in your procedure is that ExitCond needs to be reinitialized to false for each value of k.

A minor issue is that a procedure should declare the modules (or packages) that it uses. Make the first line of the procedure

uses LinearAlgebra, Statistics;

Here is Maple code for the above algorithm. The return value is a list of the m-1 centers (each a Vector), followed by the common radius. You did not say that the balls needed to lie entirely within the bounds, merely that their centers did, so I have not required that.

Balls:= proc(
   Box::range(Vector(realcons)), #range for each dimension
   X1::Vector(realcons), #initial ball's center
   R1::And(realcons, positive), #initial ball's radius
   m::posint #number of balls (incl. initial)
)
uses LA= LinearAlgebra, C= combinat;
local
   d:= numelems(X1), #number of dimensions
   L:= lhs(Box), #lower bounds
   U:= rhs(Box), #upper bounds
   M:= U-L, #magnitudes of dimensions 
   RV:= proc()
   local 
      RV:= (()-> LA:-RandomVector(d, 'generator'= 0. .. 1.) *~ M + L),
      rv:= RV()
   ;
      while LA:-Norm(rv - X1, 2) <= R1 do rv:= RV() end do;
      rv
   end proc,
   X:= ['RV'() $ m-1]
;
   X, 
   min(
      LA:-Norm~((`-`@op)~(C:-choose(X,2)), 2)[], #pairwise distances
      (LA:-Norm~(map(`-`, X, X1), 2) -~ R1)[] #distances from initial ball
   ) / 3
end proc
:

Example usage:

Balls(<-1,-1,-1>..<1,1,1>, <.1,.2,.3>, 0.6, 15);

Would someone please define alpha and alpha channel for me?

@Carl Love The Question has been changed a few times since I posted my Answer above. My Answer pertained to something like

plot(-x^2+1, x= -1..1);

which was at the end of the Question as an example of something much simpler that gave the same error message. It was this that I was responding to. This line has no error.

@Jayaprakash J No, you do not need Mathematica to do this.

It would be better to totally omit the output from your Questions than to include it unformatted. The inclusion of the output makes the input more difficult to see.

I saw a few minutes ago that you had another question, about pseudo-differential operators. But that's gone now. Please repost that, preferably in a new Question thread.

@Mayo_Kun What are the units, or at least the dimensions, of f, of theta, and of eta? This is a fluid dynamics problem, right? There must be something in the physics of the problem that allows the 2nd derivative of f to be raised to the 0.4 power.

First 252 253 254 255 256 257 258 Last Page 254 of 709