Cacher is the code snippet organizer for pro developers

<?php
//in register post type args array set rewrite to:
'rewrite' => array(
	'slug' => 'mycpt',
	'with_front' => false,
	'feeds' => false,
	'pages' => true
)

//then add this to functions.php
add_action('init', 'mycpt_rewrite');
function mycpt_rewrite() {
  global $wp_rewrite;
  $queryarg = 'post_type=mycpt&p=';
  $wp_rewrite->add_rewrite_tag('%cpt_id%', '([^/]+)', $queryarg);
  $wp_rewrite->add_permastruct('mycpt', '/mycpt/%cpt_id%', false);
}

add_filter('post_type_link', 'mycpt_permalink', 1, 3);
function mycpt_permalink($post_link, $id = 0, $leavename) {
  global $wp_rewrite;
  $post = &get_post($id);
  if ( is_wp_error( $post ) )
    return $post;
  $newlink = $wp_rewrite->get_extra_permastruct('mycpt');
  $newlink = str_replace("%cpt_id%", $post->ID, $newlink);
  $newlink = home_url(user_trailingslashit($newlink));
  return $newlink;
}

//and make sure you change all "mycpt" to the name of you custom post type.