algorithm - Minimum count of numbers to be inserted in [a,b] such that GCD of 2 consecutive numbers is 1 -


this question asked in topcoder - srm 577. given 1 <= < b <= 1000000, minimum count of numbers inserted between a & b such no 2 consecutive numbers share positive divisor greater 1.

example:

  1. a = 2184; b = 2200. need insert 2 numbers 2195 & 2199 such condition holds true. (2184,2195,2199,2200)
  2. a = 7; b= 42. 1 number sufficient insert between them. number can 11.
  3. a = 17;b = 42. gcd 1, no need insert number.

now, interesting part given range [1,1000000] never require more 2 elements inserted between a , b. more, 2 numbers speculated a+1 , b-1 though yet proven.

  1. can prove this?
  2. can extended larger range of numbers also? say, [1,10^18] etc

doh, sorry. counterexample have is

a=3199611856032532876288673657174760 b=3199611856032532876288673657174860

(would nice if stupid site allowed edit posts)


Comments

Post a Comment

Popular posts from this blog

linux - Does gcc have any options to add version info in ELF binary file? -

i mean whether gcc can insert source code version infor elf binary section or similar. not want change source file, add info gcc option in makefile. you can emit version info text file, turn text file object file statically link executable. the first step simple have write code: script or write version info in format plain text file. write makefile rule produce version.o version.txt, using objcopy . you'll have object file 2 useful symbols defined in it: beginning , end of textual version info. add generated object executable, , you'll able access version 2 ways: running strings on binary, or writing code in application print version string (you'll need declare start , end symbols variables in header file).
Read more

java - Are there any classes that implement javax.persistence.Parameter<T>? -

i'm using named queries fetch entities database using jpa , hibernate , came across puzzling me: how come there no default implementations of javax.persistence.parameter interface? i rather impressed how @staticmetamodel used criteriabuilder in jpa2 meaning type safety , don't have mess around setting string names. wanted apply similar of jpa1 ejb's i'm working on: dealergroup_.class: public dealergroup_ { public parameter<integer> id = new parameterimpl<integer>("id"); /// etc... } dealergroupfacade.class: // ... public dealergroup fetch(integer id) { typedquery<dealergroup> query = em.createnamedquery("dealergroup.fetchbyid", dealergroup.class); query.setparameter(dealergroup_.id, query); return query.getsingleresult(); } // ... i surprised find there no implementations of parameter interface - of course, implement myself absence makes me suspicious may mistake using in way? should implementing parameter...
Read more

android - send complex objects as post php java -

is possible send contact numbers via post php class inside eclipse ? or post limited primitive types , have find work arounds send them string ? i propose: send them json in post request, befor start, have @ gson project , keep in mind set content application -> json. luck
Read more